Dans cet article, vous trouverez des moyens de résoudre une équation de la forme $ax\equiv b \quad [n].$ Le but est d’essayer de diviser successivement le nombre $a$ jusqu’à obtenir $1$ mais certaines précautions doivent être prises.
Quand les trois coefficients admettent un diviseur commun
Fixez trois nombres entiers $a$, $b$ et $n.$ Soit à résoudre l’équation ci-dessous dont l’inconnue $x$ est un nombre entier :
\boxed{(E): \quad ax \equiv b \quad [n].}Supposez qu’il existe un entier non nul $d$ tel que :
\left\{\begin{align*}
d&\mid a\\
d&\mid b\\
d&\mid n.
\end{align*}\right.Vous notez $a’$, $b’$ et $n’$ les quotients correspondants, qui sont aussi des nombres entiers :
\left\{\begin{align*}
a' &= a/d\\
b' &= b/d\\
n' &= n/d.
\end{align*}\right.Vous considérez l’équation suivante dont l’inconnue $x$ est un nombre entier :
\boxed{(E'): \quad a'x \equiv b' \quad [n'].}Alors les équations $(E)$ et $(E’)$ ont le même ensemble de solutions.
En effet :
\begin{align*}
x\text{ est solution de }(E) &\Longleftrightarrow ax\equiv b\quad [n]\\
&\Longleftrightarrow n\mid ax- b \\
&\Longleftrightarrow \exists k\in\Z, ax- b = kn \\
&\Longleftrightarrow \exists k\in\Z, da'x- db' = kdn' \\
&\Longleftrightarrow \exists k\in\Z, d(a'x- b') = kdn' \\
&\Longleftrightarrow \exists k\in\Z, a'x- b' = kn' \\
&\Longleftrightarrow n' \mid a'x- b' \\
&\Longleftrightarrow a'x\equiv b'\quad [n]\\
&\Longleftrightarrow x\text{ est solution de }(E').
\end{align*} Note. Si équation de la forme $ax\equiv b\quad [n]$ possède au moins une solution, alors $b$ est nécessairement divisible $PGCD(a,n).$
Dans la suite, vous vous attachez à une équation linéaire avec congruence, en supposant désormais que $PGCD(a,n)=1.$
Quand $a$ est premier avec $n$ la congruence modulo $n$ est conservée après une division
Fixez trois nombres entiers $a$, $b$ et $n.$ Vous supposez que $PGCD(a,n)=1$ et qu’il existe un entier non nul $d$ tel que $d\mid a$ et $d\mid b.$ Comme précédemment, vous posez :
\left\{\begin{align*}
a' &= a/d\\
b' &= b/d.
\end{align*}\right.Alors les équations suivantes possédant la même congruence modulo $n$ ont le même ensemble de solutions :
\begin{align*}
(E): \quad ax &\equiv b \quad [n]\\
(E'): \quad a'x &\equiv b' \quad [n].
\end{align*}Première étape. Soit $x$ une solution de l’équation $(E’).$ Alors $n \mid a’x-b’.$ Or $ax-b = da’x-db’ = d(a’x-b’).$ Donc $a’x-b’ \mid ax-b.$ Par transitivité, vous déduisez $n \mid ax-b$ et par suite $ax\equiv b \quad [n]$ et $x$ est solution de $(E).$
Seconde étape. Soit maintenant $x$ une solution de $(E).$ Alors $n \mid ax-b$ ce qui s’écrit $n\mid d(a’x-b’).$ Par définition, $PGCD(n,d)$ divise $d.$ Or $d\mid a$ et par transitivité $PGCD(n,d) \mid a.$ Toujours avec la définition du $PGCD$, $PGCD(n,d) \mid n.$ Comme $PGCD(n,d)$ divise à la fois $a$ et $n$ qui sont premiers entre eux, il en résulte que $PGCD(n,d)=1.$ En appliquant le théorème de Gauss, $n\mid d(a’x-b’)$ fournit $n\mid a’x-b’$ et $a’x\equiv b’\quad [n]$ et $x$ est solution de $(E’).$
Appliquez les résultats précédents sur des exemples
Résolvez l’équation $3x\equiv 4\quad [5]$
Vous remarquez que $PGCD(3,5)=1.$ La stratégie va consister à remplacer $4$ par un nombre congru modulo $5$ qui est aussi un multiple de $3.$
Or, vous avez :
\begin{align*}
4 &\equiv 4+5\quad [5]\\
&\equiv 9\quad [5].
\end{align*} Vous pouvez diviser par $3$ à la dernière étape pour conclure :
\begin{align*}
3x\equiv 4\quad [5] \Longleftrightarrow 3x\equiv9\quad [5]\\
\Longleftrightarrow x\equiv3 \quad [5].
\end{align*}L’ensemble des solutions de cette équation est :
\mathscr{S} = \{3+5k, k\in\Z\}.Résolvez l’équation $18x\equiv 42\quad [50]$
Vous calculez d’abord $PGCD(18,50)$ en utilisant le fait que $PGCD(9,25)=1$ combiné avec la propriété multiplicative du $PGCD.$
\begin{align*}
PGCD(18,50) &= 2PGCD(9,25)\\
&= 2\times 1\\
&=2.
\end{align*}La congruence modulo $50$ se simplifie en une congruence modulo $25.$
\begin{align*}
18x\equiv 42\quad [50] \Longleftrightarrow 9x\equiv 21\quad [25].
\end{align*}Vous allez maintenant ajouter ou soustraire $25$ un certain nombre de fois à $21$ jusqu’à tomber sur un multiple de $9.$
\begin{align*}
9x\equiv 21\quad [25] &\Longleftrightarrow 9x\equiv 21\quad [25]\\
& \Longleftrightarrow 9x\equiv 46\quad [25] \\
&\Longleftrightarrow 9x\equiv 71\quad [25] \\
&\Longleftrightarrow 9x\equiv 96\quad [25] \\
&\Longleftrightarrow 9x\equiv 121\quad [25] \\
&\Longleftrightarrow 9x\equiv 146\quad [25] \\
&\Longleftrightarrow 9x\equiv 171\quad [25] \\
&\Longleftrightarrow 9x\equiv 19\times 9\quad [25]\\
&\Longleftrightarrow x\equiv 19\quad [25].
\end{align*}L’ensemble des solutions de cette équation est :
\mathscr{S} = \{19+25k, k\in\Z\}.La méthode ci-dessus fonctionne systématiquement
Fixez trois nombres entiers $a$, $b$ et $n.$ Vous supposez que $PGCD(a,n)=1.$ Vous allez démontrer qu’il existe un entier $q$ tel que $a\mid b+qn.$
En effet, comme $a$ et $n$ sont deux entiers premiers entre eux, en appliquant le théorème de Bezout, il existe deux entiers $u$ et $v$ tels que $au+nv = 1.$ En multipliant par $b$, il vient :
\begin{align*}
&b= abu+bvn\\
&b+(-bv)n = abu.
\end{align*}
En posant $q= -bv$ vous avez l’égalité $b+qn = abu$ si bien que $a\mid b+qn.$
Cela justifie la technique utilisée dans l’exemple précédent.
Quand vous cherchez à résoudre $9x\equiv 21\quad [25]$, vous savez à l’avance qu’il existe un entier $q$ tel que $9 \mid 21+25q.$ Pour un tel entier, vous avez :
\begin{align*}
9x\equiv 21\quad [25] &\Longleftrightarrow 9x\equiv 21 + 25q\quad [25].
\end{align*}En notant $h$ le quotient de la division de $21+25q$ par $9$, vous aboutissez à :
\begin{align*}
9x\equiv 21\quad [25] &\Longleftrightarrow x\equiv h\quad [25].
\end{align*}La division par $9$ est autorisée sans modifier la congruence modulo $25$ puisque $PGCD(9,25)=1.$
