Home

MPSI/PCSI

Révisions Maths lycée

Arithmétique Maths expertes

PGCD

Dans cet exercice, on cherche à trouver les entiers naturels n pour lesquels le PGCD de 2n + 3 et de n est égal à 3. 

On utilise l'algorithme d'Euclide pour trouver le PGCD. En faisant la division euclidienne de 2n + 3 par n, on obtient 2n + 3 = 2 * n + 3. 

Le PGCD étant égal à 3, cela signifie que le dernier reste non nul est égal à 3. Donc, si on divise n par 3, il doit rester un reste nul, ce qui montre que n est divisible par 3. 

Ainsi, si le PGCD de 2n + 3 et de n est égal à 3, alors n est multiple de 3. 

Ensuite, on cherche les entiers naturels n pour lesquels le PGCD de 2n + 3 et de n est égal à 1. 

Si n est multiple de 3, cela est exclu car on a montré que le PGCD serait égal à 3. 

On suppose donc que n peut s'écrire sous la forme 3k + 2. En faisant la division euclidienne de 2n + 3 par n, on obtient 2n + 3 = 2 * n + 3. En divisant n par 3, on obtient n = 3 * k + 2. 

En continuant l'algorithme d'Euclide, on divise 3 par 2 et on obtient 3 = 2 * 1 + 1. Le dernier reste non nul est égal à 1, donc le PGCD de 2n + 3 et de n est égal à 1 lorsque n peut s'écrire sous la forme 3k + 2. 

De plus, si n s'écrit sous la forme 3k + 1, on obtient le même résultat en faisant l'algorithme d'Euclide. 

Finalement, si n n'est pas multiple de 3, le PGCD de 2n + 3 et de n est égal à 1.

Salut ! Dans cet exercice, on va voir un exo avec un PGCD qui va dépendre de n. Donc la première question, on nous dit déterminer l'ensemble des entiers naturels n, tels que le PGCD de 2n plus 3 et de n vaut 3. Alors là, on va penser à faire la division euclidienne de 2n plus 3 par n, enfin l'algorithme d'euclide, pardon, division euclidienne de ces nombres-là, pour que le PGCD vale 3. Donc si on fait l'algorithme d'euclide, ça veut dire qu'on divise 2n plus 3 par n, donc 2n plus 3, il est déjà divisé par ça, donc 2n plus 3, c'est 2 fois n plus 3. Voilà, c'est déjà la division euclidienne. Donc 3, c'est le PGCD. Donc si c'est le PGCD, ça veut dire que c'est le dernier reste non nul. Donc si on fait n divisé par 3, on sait qu'il y a un reste nul. Donc ça veut dire qu'il existe un q appartenant à z, bon, q appartient même à n en réalité, tel que n est égal à 3 fois q plus 0, d'accord ? C'est la division euclidienne de n par 3. Et du coup, ça veut dire que n est divisible par 3. Donc finalement, si le PGCD de 2n plus 3 et de n est égal à 3, n est multiple de 3. Ensuite, on nous dit en déduire l'ensemble des entiers naturels n, tel que le PGCD de 2n plus 3 et de n vaut 1. Là, déjà, ce qu'il faut se dire, c'est que le fait que... Enfin, quand n est multiple de 3, c'est exclu, parce qu'on a montré que si n est multiple de 3, le PGCD, c'est 3. Là, on veut que ce soit égal à 1. On veut qu'il soit premier entre eux. On va regarder tout simplement ce qui se passe si n s'écrit comme 3 fois k plus 2. Ça veut dire que si le reste de la division euclidienne de n par 3, c'est 2. Donc, 2n plus 3, on l'écrit comme 2 fois n plus 3, d'accord ? On fait encore la division euclidienne. Mais n, c'est 3 fois k plus 2. C'est-à-dire que si on divise n par 3, on l'écrit comme ça. On continue l'algorithme d'euclide en divisant 3 par 2. Donc, ça fait 3, c'est égal à 2 fois 1 plus 1. Si on tombe sur 1, c'est toujours le dernier reste non nul. Donc, finalement, le PGCD de 2n plus 3 et de n vaut 1 quand on peut écrire n comme 3k plus 2. Maintenant, il y a une autre façon qu'on n'a pas vue, ici, c'est si on écrit n comme 3 fois k. Ici, c'est 3 fois k plus 2. Il reste 3 fois k plus 1 à regarder. Si n s'écrit comme 3 fois k plus 1, on fait la même chose. Même principe, on fait l'algorithme d'euclide. Donc, on fait la division par n de 2n plus 3. C'est 2 fois n plus 3. Ensuite, on fait la division de n par 3. Cette écriture-là nous dit que c'est 3 fois k plus 1. On est tombé sur 1, c'est forcément le dernier reste non nul, donc le PGCD. Donc, le PGCD de 2n plus 3 et de n est égal à 1. Donc, finalement, si n n'est pas multiple de 3, le PGCD de 2n plus 3 et de n vaut 1.

PGCD qui dépend de n

RELATED

Recommended videos

Déterminer un PGCD

Différence et quotient