Home

Terminale

Maths Expertes

Arithmétique

PGCD

Dans cet exercice de mathématiques, nous manipulons le PGCD et des congruences. Le système S établit que n est congruent à 1 modulo 5 et à 5 modulo 7. Nous devons montrer que si n vérifie le système S, alors il vérifie également un autre système. Nous montrons cela en utilisant des congruences et en utilisant le corollaire du théorème de Gauss. Nous en déduisons que 4n est congruent à moins 1 modulo 35, et en résolvant cette équation, nous obtenons que l'ensemble des solutions est {26 + 35k | k ∈ Z}.

Salut! Dans cet exercice, on va manipuler du PGCD et des congruences. On nous donne un système S, un système de congruence. On nous dit que n est congruent à 1 modulo 5, et congruent à 5 modulo 7. On nous dit, montrez que si n vérifie le système S, alors n vérifie ce système-là. En gros, ça veut dire montrer une équivalence entre les deux systèmes. Bon, c'est parti! Donc, première ligne du système, c'est n congrue à 1 modulo 5. Si n est congrue à 1 modulo 5, nous ce qui nous intéresse, c'est de voir modulo 5, 4n plus 1, c'est congru à combien? 4n c'est congru à 4, d'accord? On multiplie ça par 4. Donc 4n est congru à 4 modulo 5. Et étant donné que 4, c'est moins 1 modulo 5, on remplace le 4 par moins 1, on passe le moins 1 de l'autre côté, ça nous donne plus 1. Donc 4n plus 1 est bien congrue à 0 modulo 5. Ensuite, la deuxième ligne, si n est congrue à 5 modulo 7, 4n est congrue à 20 modulo 7, mais 20 c'est pareil, c'est moins 1, parce qu'au-dessus, on multiplie le 7, il y a 21. 21, c'est 20 plus 1, donc plutôt 20, c'est 21 moins 1. Donc 20 est congrue à moins 1 modulo 7, et donc, même principe, on passe le moins 1 de l'autre côté, donc ça nous fait 4n plus 1 est congrue à 0 modulo 7. Ensuite, on nous dit en déduire alors que 4n est congrue à moins 1 modulo 35. Donc là, ce qu'on va faire, c'est déjà, on va regarder un peu pourquoi on nous parle de 35, tout ça. Donc on sait que 5 divise 4n plus 1, et 7 divise 4n plus 1 aussi. Donc petit rappel, le corollaire du théorème de Gauss, si A divise C, B divise C, et que le PGCD de A et de B vaut 1, alors AB divise C, le produit des deux divise C. Ensuite, là, c'est ça qu'on va utiliser. 5 et 7 sont premiers entre eux, donc d'après le corollaire du théorème de Gauss, le produit des deux divise aussi 4n plus 1. Donc finalement, 4n plus 1 est congrue à 0 modulo 35, c'est ça que nous dit cette information-là. Donc 4n est congrue à moins 1 modulo 35. Et ça, ça répond à la question. La question 2, c'est directement en déduire les solutions de S. On va se servir de ce qu'on a déjà fait. Donc 4n, on sait qu'il est congru à moins 1 modulo 35. Ça, c'est l'information que ce système-là nous donne. Et on cherche à trouver n, on cherche à isoler n. Mais on ne peut pas le diviser par 4 comme on ferait avec une équation classique. Donc là, la méthode, quand on a une équation comme ça avec des entiers, c'est, pour résoudre une équation AX congrue à B modulo n, ce qu'on fait, c'est qu'on va chercher un k dans un n, donc l'intervalle 1, n, alors qu'on a des doubles barres comme ça sur l'intervalle, c'est qu'on ne regarde que les entiers de 1 à n. Donc on cherche un k qui vérifie que A, donc le coefficient devant le X, A fois k est congru à 1 modulo n. Donc en gros, on peut le voir comme un inverse dans la classe d'équivalence modulo n, mais on ne parle pas trop de ça pour l'instant. On dit juste qu'il y a un k tel que quand on multiplie A par k, on tombe sur 1 modulo n. Et du coup, ce qu'on fait pour simplifier par A, enfin pour faire sauter le A, on va multiplier par ce k à gauche et à droite, on fait A fois k et B fois k, et du coup, A fois k ça fait 1. C'est exactement ça qu'on utilise. Et donc, on se retrouve avec juste X congrue à quelque chose modulo n, et ce sera ça, nos solutions. C'est ce qu'on va faire. On repart de 4n congrue à moins 1 modulo 35, et on cherche 4, on doit multiplier 4 par quoi pour avoir 1 modulo 35, il y en a un qui vient à ça, évidemment, c'est 36, parce que 36 c'est 4 fois 9, et ça c'est congrue à 1 modulo 35, parce que 36 c'est 35 plus 1, donc c'est congrue à 1. Donc on va multiplier par 9. Donc finalement, 4n congrue à moins 1 modulo 35, on multiplie par 9, ça nous fait 36n congrue à moins 9 modulo 35, donc n est congrue à 26 modulo 35, moins 9 c'est 26 modulo 35, on fait moins 9 plus 35, ça nous fait 26. Donc, finalement, l'ensemble des solutions, c'est tous les nombres qui s'écrivent 26 plus 35k, avec k qui appartient à z.

PGCD et congruences

RELATED

Recommended videos

Déterminer un PGCD

Différence et quotient

PGCD qui dépend de n