Penchons-nous à présent sur la résolution de l'équation
$$a x \equiv b \pmod n$$ où $a, b \in \mathbb{Z}_0$ et $n \in \mathbb{N}_0$ sont fixés alors que $x$ est l'inconnue.
Le cas où $(a, n) = 1$
Si $a$ et $n$ sont premiers entre eux, alors $a$ possède un inverse modulo $n$, comme nous l'avons-vu dans le point théorique précédent.
Nous notons $a^{-1}$ cet inverse et pouvons donc multiplier les deux membres de l'égalité par $a^{-1}$ pour obtenir l'équation équivalente
$$ x \equiv a^{-1}b \pmod n$$ qui nous donne donc immédiatement la solution à notre équation de départ : il s'agit des $x$ congrus à $a^{-1}b$ modulo $n$.
Le cas où $(a, n) \neq 1$
Si $a$ et $n$ ne sont pas premiers entre eux, on note $(a, n) = d \neq 1$. Vu que $d$ divise $a$ et $n$, on peut noter $a = d\cdot a'$ et $n = d\cdot n'$. On a alors $(a', n') = 1$ puisque nous avons divisé $a$ et $n$ par tous les facteurs communs qu'ils avaient.
Deux cas se présentent alors :
- Si $b$ n'est pas divisible par $d$, alors il n'y a aucune chance de trouver un $x$ tel que $ax - b$ soit divisible par $n$, puisqu'il n'est en particulier pas divisible par $d$. Dans ce cas, l'équation ne possède pas de solution.
- Si $b$ est divisible par $d$, alors on pose $b = d \cdot b'$ et l'équation se réécrit
$$da' x \equiv d b' \pmod{d n'}.$$ Or, $d a' x - d b'$ est divisible par $d n'$ si et seulement si $a' x - b'$ est divisible par $n'$, ce qui nous permet de simplifier tous les $d$ pour nous ramener à
$$ a' x \equiv b' \pmod{n'}.$$
Vu que $(a', n') = 1$, nous nous sommes ramenés au premier cas et pouvons multiplier les deux membres par l'inverse $a'^{-1}$ de $a$ pour trouver
$$x \equiv a'^{-1} b' \pmod {n'}$$ ce qui signifie que la solution est donnée par les $x$ congrus à $a'^{-1} b'$ modulo $n'$.
Exemples
- Considérons l'équation
$$4x \equiv 2 \pmod {7}.$$ Vu que $(4,7) = 1$, nous sommes dans le premier cas. On cherche alors l'inverse de $4$ modulo $7$. On peut utiliser l'algorithme d'Euclide mais il est ici aisé de remarquer qu'il s'agit de $2$ vu que $4\cdot 2 \equiv 8 \equiv 1 \pmod 7$. On multiplie alors les deux membres par $2$ et on obtient
$$x \equiv 4 \pmod 7.$$ L'ensemble des solutions est donc l'ensemble des $x$ congrus à $4$ modulo $7$ : $x \in \left\{\dots, -10, -3, 4, 11, \dots \right\}$.
- Considérons l'équation
$$ 6x \equiv 9 \pmod{15}.$$ Ici, $(6,15) = 3$. Mais $b = 9$ est également divisible par $3$, donc nous pouvons diviser les trois nombres par $3$ pour nous ramener à
$$ 2x \equiv 3 \pmod 5.$$ On procède alors comme précédemment, en multipliant les deux termes par $3$, l'inverse de $2$ modulo $5$ :
$$ x \equiv 9 \equiv 4 \pmod 5.$$ L'ensemble des solutions est donc l'ensemble des $x$ congrus à $4$ modulo $5$.
- Considérons l'équation
$$ 4x \equiv 5 \pmod{14}.$$ Ici, $(4,14) = 2$. Mais $b = 5$ n'est pas divisible par $2$, et il n'y a donc aucune solution à cette équation.