Home

2BAC SM Maroc

Maths SM&SP

Algèbre

PGCD

Salut ! Dans cet exercice, nous devons démontrer une équivalence entre deux systèmes de congruence. Le premier système nous dit que n est congruent à 1 modulo 5 et congruent à 5 modulo 7. Pour montrer que si n satisfait ce système, alors il satisfait également l'autre système, nous manipulons les congruences. 

Pour la première congruence, n congruent à 1 modulo 5, nous nous intéressons à 4n plus 1 modulo 5. En multipliant cette expression par 4, nous obtenons que 4n est congruent à 4 modulo 5. Comme 4 est équivalent à -1 modulo 5, nous remplaçons 4 par -1. Ainsi, nous obtenons que 4n plus 1 est congruent à 0 modulo 5.

Pour la deuxième congruence, si n est congruent à 5 modulo 7, alors 4n est congruent à 20 modulo 7. Comme 20 est équivalent à -1 modulo 7, nous remplaçons 20 par -1. Donc 4n plus 1 est congruent à 0 modulo 7.

En utilisant le corollaire du théorème de Gauss, qui dit que si A divise C, B divise C, et que le PGCD de A et B vaut 1, alors AB divise C, nous pouvons déduire que 4n plus 1 est congruent à 0 modulo 35. Cela est possible car 5 et 7 sont premiers entre eux. 

Maintenant, pour trouver les solutions du système S, nous utilisons l'information précédente selon laquelle 4n est congruent à -1 modulo 35. Nous devons trouver une valeur k dans les entiers de 1 à 35 telle que 4k est congruent à 1 modulo 35. En multipliant chaque côté par 9, nous trouvons que 4n est congruent à -9 modulo 35. Ainsi, n est congruent à 26 modulo 35.

En résumé, les solutions du système S sont tous les nombres de la forme 26 plus 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