PGCD et congruences

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.