352. Résolvez une équation avec congruence dans le cas linéaire

Dans ce contenu, 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\comma$ $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’\comma$ $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, comme $d$ est non nul, vous pouvez simplifier par $d$ à la cinquième ligne :

\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 une équation de la forme $ax\equiv b\quad [n]$ possède au moins une solution $x\comma$ alors il existe un entier $k$ tel que $b = ax-kn.$ Comme $\pgcd(a,n)$ divise $a$ et $n\comma$ il divise $b.$ Ainsi, $b$ est nécessairement divisible par $\pgcd(a,n).$

Dans ce cas, en divisant $a\comma$ $b$ et $n$ par $\pgcd(a,n)$ comme ci-dessus, vous vous ramenez à une équation de même ensemble de solutions dont le coefficient et le module sont premiers entre eux. Dans la suite, vous supposez donc désormais que $\pgcd(a,n)=1.$

Quand $a$ est premier avec $n\comma$ la congruence modulo $n$ est conservée après une division

Fixez trois nombres entiers $a\comma$ $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 par définition du $\pgcd\comma$ $\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*}

D’après la section précédente, comme $\pgcd(3,5)=1\comma$ 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) &= 2\pgcd(9,25)\\ &= 2\times 1\\ &=2. \end{align*}

Comme $2$ divise $18\comma$ $42$ et $50\comma$ d’après la première section, la congruence modulo $50$ se simplifie en une congruence modulo $25.$

18x\equiv 42\quad [50] \Longleftrightarrow 9x\equiv 21\quad [25].

Vous allez maintenant ajouter $25$ un certain nombre de fois à $21$ jusqu’à tomber sur un multiple de $9.$

\begin{align*} 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*}

La dernière équivalence découle de la section précédente, puisque $\pgcd(9,25)=1.$ 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\comma$ $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 Bézout, il existe deux entiers $u$ et $v$ tels que $au+nv = 1.$ En multipliant par $b\comma$ 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]\comma$ vous savez à l’avance qu’il existe un entier $q$ tel que $9 \mid 21+25q.$ Pour un tel entier, vous avez :

9x\equiv 21\quad [25] \Longleftrightarrow 9x\equiv 21 + 25q\quad [25].

En notant $h$ le quotient de la division exacte de $21+25q$ par $9\comma$ vous aboutissez à :

9x\equiv 21\quad [25] \Longleftrightarrow x\equiv h\quad [25].

La division par $9$ est autorisée sans modifier la congruence modulo $25$ puisque $\pgcd(9,25)=1.$