All subjects
- All subjects
Equation modulaire
Dans cet exercice, on cherche à trouver les solutions de l'équation AX congruent à B modulo N, avec des conditions sur A, B et N. On veut démontrer que cette équation a une solution si et seulement si le PGCD de A et N divise B.
Dans la première partie, on montre que si X est une solution de l'équation, alors le PGCD divise B. On utilise le fait que si AX est congruent à B modulo N, cela signifie que le PGCD de A et N divise B.
Dans la deuxième partie, on montre que si le PGCD divise B, alors l'équation a une solution. On utilise le théorème de Bézout pour montrer qu'il existe un nombre UV tel que AU + NV est égal à D. En multipliant cette équation par B, on obtient BAU + BNV = BD. En factorisant B par le PGCD, on obtient l'équation B'AU + B'NV = B. On en déduit que B'U est une solution de l'équation.
Dans la deuxième question, on suppose que le PGCD divise B et on pose N égale à DN'. On veut montrer que l'ensemble des solutions de l'équation est donné par X0 + QN', où Q est un entier. On utilise le fait que si X est une solution, alors A(X-X0) est congruent à 0 modulo N. En factorisant A par le PGCD, on obtient l'équation A'(X-X0) = KN'. Comme A' et N' sont premiers entre eux, on en déduit que N' divise X-X0. On peut alors montrer que tous les nombres de la forme X0 + QN' sont des solutions de l'équation.
Dans la troisième question, on cherche à montrer que deux solutions de l'équation sont congrues entre elles modulo N si et seulement si le PGCD divise la différence de leurs coefficients multiplicateurs. On en déduit que les solutions de l'équation sont de la forme X0 + QN', où Q est un entier et X0 est une solution particulière. On conclut que l'équation admet exactement ces solutions.
