Dans le contenu rédigé dans l'article 352 une méthode permettant de résoudre une équation linéaire avec congruences a été développée.
Sera présentée ici une méthode alternative qui ne fait pas appel au $PGCD$ directement.
Soit $a$ un entier naturel non nul, $b$ un entier relatif et $n$ un entier naturel non nul.
Vous souhaitez résoudre l’équation suivante d’inconnue $x$ entière :
ax\equiv b\mod n.
Remarquez que vous pouvez remplacer $a$ et $b$ respectivement par leurs résidus modulo $n.$
Autrement dit, dans la suite, vous supposez que $a$ est un entier naturel non nul strictement inférieur à $n$, que $b$ est un entier naturel strictement inférieur à $n.$
Le théorème fondamental
Vous effectuez la division euclidienne de $n$ par $a$, il existe un quotient $q\in\N$ et un reste $r\in\N$ avec $0\leq r \leq a-1$ tels que $n = aq+r.$
Vous allez établir que l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution, si et seulement si, l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution.
Premier sens
Soit $x\in\Z$ tel que $ax\equiv b \mod n.$
Il existe un entier relatif $k$ tel que $ax = b+ nk.$ Vous remplacez $n$ par $aq+r$ du coup :
\begin{align*}
ax &= b +(aq+r)k\\
ax &= b +aqk+rk\\
a(x-qk) - b &= rk.
\end{align*}Cela prouve que $rk \equiv -b \mod a.$
Donc l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution qui est $k.$
Second sens
Soit $y\in\Z$ tel que $ry \equiv -b \mod a.$
Il existe un entier relatif $t$ tel que $ry = -b+at.$ Vous utilisez le fait que $r = n-aq$ ce qui fournit :
\begin{align*}
(n-aq)y = -b+at\\
ny-aqy = -b+at\\
ny+b = a(t+qy).
\end{align*}Cela prouve que $a(t+qy) \equiv b \mod n.$ Or, $t+qy\in\Z.$
Donc l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution qui est $t+qy.$
Déduisez une solution de l’équation $ax\equiv b\mod n$ à partir d’une solution de l’équation $ry\equiv -b\mod a$
Soit $y$ un entier relatif tel que $ry\equiv -b \mod a.$
Alors $a$ divise $ry+b.$ Donc $t = \frac{ry+b}{a}$ est un nombre entier et $ry = -b+at.$
D’après le calcul effectué à la section précédente, si vous posez $x = t+qy$, alors $x$ est un entier relatif et $ax\equiv b\mod n.$
Vous trouvez maintenant une expression de $x$ qui ne fait pas intervenir le quotient $q.$ En effet :
\begin{align*}
x &= t+qy\\
&=\frac{ry+b}{a}+\frac{aqy}{a}\\
&=\frac{(aq+r)y+b}{a}\\
&=\frac{ny+b}{a}.
\end{align*}Vous utiliserez dans la suite :
\boxed{x=\frac{ny+b}{a}.}En définitive, si $k$ est une solution de l’équation $ry \equiv -b \mod a$, alors $\frac{nk+b}{a}$ est une solution de l’équation $ax\equiv b\mod n.$
Note. Au passage, comme $x$ est un entier relatif, vous constatez que le nombre $a$ divise $ny+b.$ Cela peut se voir depuis le début. Comme $ry\equiv -b \mod a$ vous avez $(n-aq)y \equiv -b \mod a$ si bien que $ny\equiv -b \mod a$ et $ny+b\equiv 0 \mod a.$
Application
L’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ admet-elle au moins une solution ? Si oui, en déterminer une.
Vous appliquez le théorème fondamental précité pour le savoir.
Vous effectuez la division euclidienne de $231$ par $143.$ Comme $231 = 1\times 143+88$ Vous trouvez un reste égal à $88.$
Il s’agit maintenant de savoir si l’équation $88 y_1\equiv -44 \mod 143$ d’inconnue $y_1\in\Z$ admet au moins une solution.
Vous effectuez la division euclidienne de $143$ par $88.$ Comme $143 = 1\times 88+55$ Vous trouvez un reste égal à $55.$
Il s’agit maintenant de savoir si l’équation $55 y_2 \equiv 44 \mod 88$ d’inconnue $y_2\in\Z$ admet au moins une solution.
En divisant par $11$ cette équation est équivalente à $5y_2\equiv 4 \mod 8.$
Vous effectuez la division euclidienne de $8$ par $5.$ Comme $8 = 1\times 5+3$ Vous trouvez un reste de $3.$
Il s’agit maintenant de savoir si l’équation $3 y_3 \equiv -4 \mod 5$ d’inconnue $y_3\in\Z$ admet au moins une solution.
Vous effectuez la division euclidienne de $5$ par $3.$ Comme $5= 1\times 3+2$ Vous trouvez un reste de $2.$
Il s’agit maintenant de savoir si l’équation $2 y_4 \equiv 4 \mod 3$ d’inconnue $y_4\in\Z$ admet au moins une solution.
Vous effectuez la division euclidienne de $3$ par $2.$ Comme $3= 1\times 2+1$ Vous trouvez un reste de $1.$
Vous tombez alors sur l’équation $y_5 \equiv -4 \mod 2$ d’inconnue $y_5\in\Z$ qui admet au moins une solution, il suffit de prendre $y_5 = 0.$ Il s’ensuit que toutes les équations précitées admettent au moins une solution. Pour chacune d’entre elles, vous en calculez une.
Il vient successivement :
\begin{align*}
y_4 &= \frac{3y_5+4}{2} = \frac{4}{2} = 2
\\
y_3 &= \frac{5y_4-4}{3} = \frac{10-4}{3} = 2
\\
y_2 &= \frac{8y_3+4}{5} = \frac{16+4}{5} = 4
\\
y_1 &= \frac{143y_2-44}{88} = \frac{572-44}{88} = \frac{528}{88} = 6
\\
x&=\frac{231y_1+44}{143} = \frac{1386+44}{143}=10.
\end{align*} En définitive, $10$ est une solution de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z.$
Prolongement
Déterminez toutes les solutions de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ en les décrivant modulo $231.$
Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !