All subjects
All subjects
PGCD et congruences
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.