Une méthode permettant de résoudre une équation linéaire avec congruences a été développée dans un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 352.

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$ entier relatif :

Remarquez que vous pouvez remplacer $a$ et $b$ respectivement par leurs résidus modulo $n.$ Si le résidu de $a$ est nul, la variable $x$ disparaît et l’équation est immédiatement résolue.

Autrement dit, dans la suite, vous supposez que $a$ est un entier naturel non nul strictement inférieur à $n\comma$ et que $b$ est un entier naturel strictement inférieur à $n.$

Le théorème fondamental

En effectuant la division euclidienne de $n$ par $a\comma$ vous obtenez 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 :

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 :

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.$

Note. Aucune des deux démonstrations n’utilise l’hypothèse $0\leq b \lt n.$ Le théorème fondamental reste valable lorsque $b$ est un entier relatif quelconque.

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\comma$ 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 :

Vous utiliserez dans la suite :

En définitive, si $k$ est une solution de l’équation $ry \equiv -b \mod a\comma$ 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\comma$ 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\comma$ 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.

Comme $11$ divise $55\comma$ $44$ et $88\comma$ l’entier $88$ divise $55y_2-44$ si et seulement si $8$ divise $5y_2-4.$ En divisant par $11\comma$ cette équation est donc équivalente à $5y_2\equiv 4 \mod 8.$

Vous effectuez la division euclidienne de $8$ par $5.$ Comme $8 = 1\times 5+3\comma$ 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\comma$ 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\comma$ 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 :

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.$