Home

MPSI/PCSI

Révisions Maths lycée

Arithmétique Maths expertes

PGCD

Dans cet exercice, nous devons montrer une équivalence entre deux systèmes de congruence. 
Le premier système stipule que 'n' est congruent à 1 modulo 5 et congruent à 5 modulo 7. 
Pour prouver cela, nous examinons les deux lignes du système. 
Dans la première ligne, nous remarquons que si 'n' est congruent à 1 modulo 5, alors 4n + 1 est congruent à 0 modulo 5. 
Dans la deuxième ligne, si 'n' est congruent à 5 modulo 7, alors 4n + 1 est congruent à 0 modulo 7. 
En utilisant le corollaire du théorème de Gauss, qui stipule que si deux nombres A et B sont premiers entre eux et divisent un nombre C, leur produit AB divise également C, nous concluons que 5 et 7 étant premiers entre eux, leur produit divise 4n + 1. 
Ainsi, nous obtenons que 4n + 1 est congruent à 0 modulo 35. 
Pour résoudre ce système, nous cherchons à isoler 'n'. 
En utilisant une méthode spécifique pour résoudre des équations de la forme AX congruent à B modulo n, nous trouvons un entier k tel que 4k est congruent à 1 modulo 35. 
En multipliant les deux côtés de l'équation par k, nous obtenons que 'n' est congruent à 26 modulo 35. 
Les solutions de ce système sont donc tous les nombres de la forme 26 + 35k, avec k appartenant à 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 ben, c'est parti ! Donc, première ligne du système, c'est n congruent à 1 modulo 5. Si n est congruent à 1 modulo 5, nous ce qui nous intéresse, c'est de voir modulo 5, 4n plus 1, c'est congruent à combien ? 4n c'est congruent à 4, d'accord ? On multiplie ça par 4. Donc 4n est congruent à 4 modulo 5. Et étant donné que 4, c'est moins 1 modulo 5, eh ben, 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 congruent à 0 modulo 5. Ensuite, la deuxième ligne, si n est congruent à 5 modulo 7, 4n est congruent à 20 modulo 7. Mais 20, c'est pareil, c'est moins 1, parce qu'au-dessus, en multiple de 7, il y a 21. 21, c'est 20 plus 1, donc plutôt 20, c'est 21 moins 1. Donc, 20 est congruent à 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 congruent à 0 modulo 7. Ensuite, on nous dit, on déduit alors que 4n est congruent à 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. D'accord ? 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 congruent à 0 modulo 35. D'accord ? C'est ça que nous dit cette information-là. Donc, 4n est congruent à moins 1 modulo 35. Et ça, ça répond à la question. La question 2, c'est directement en déduire les solutions de S. Eh bien, on va se servir de ce qu'on a déjà fait. Donc, 4n, on sait qu'il est congruent à 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 congruent à 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 congruent à 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, 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 congruent à quelque chose modulo n, et ce sera ça, nos solutions. C'est ce qu'on va faire. On repart de 4n congruent à 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 congruent à 1 modulo 35, parce que 36, c'est 35 plus 1, donc c'est congruent à 1. Donc on va multiplier par 9. Donc finalement, 4n congruent à moins 1 modulo 35, on multiplie par 9, ça nous fait 36n congruent à moins 9 modulo 35. Donc n est congruent à 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