Étape 1
On commence par chercher un inverse de $7$ modulo $23$, c'est-à-dire un entier $u$ tel que $7u \equiv 1 \pmod{23}$.
Étape 2
Appliquons l'algorithme d'Euclide aux entiers $23$ et $7$ :
Étape 3
$$23 = 7 \times 3 + 2$$
Étape 4
$$7 = 2 \times 3 + 1$$
Étape 5
On remonte les divisions pour exprimer $1$ en fonction de $7$ et $23$ :
Étape 6
$$1 = 7 - 2 \times 3 = 7 - (23 - 7 \times 3) \times 3$$
Étape 7
$$1 = 7 \times 10 - 23 \times 3$$
Étape 8
On en déduit l'égalité de congruence modulo $23$ :
Étape 9
$$7 \times 10 \equiv 1 \pmod{23}$$
Étape 10
Ainsi, $10$ est un inverse de $7$ modulo $23$.
Étape 11
Multiplions les deux membres de l'équation $7x \equiv 6 \pmod{23}$ par $10$ :
Étape 12
$$10 \times 7x \equiv 10 \times 6 \pmod{23}$$
Étape 13
Comme $10 \times 7 \equiv 1 \pmod{23}$, cette équation équivaut à :
Étape 14
$$x \equiv 60 \pmod{23}$$
Étape 15
Effectuons la division euclidienne de $60$ par $23$ : $60 = 23 \times 2 + 14$, avec $0 \le 14 < 23$.
Étape 16
On obtient donc :
Étape 17
$$x \equiv 14 \pmod{23}$$
Étape 18
L'unique entier solution vérifiant $0 \le x < 23$ est donc $14$.
Méthode clé
Pour résoudre $ax \equiv b \pmod n$ avec $\text{PGCD}(a, n) = 1$, on cherche $u \in \mathbb{Z}$ tel que $au \equiv 1 \pmod n$ (via l'égalité de Bézout), puis on multiplie la congruence par $u$.
Piège à éviter
Ne pas oublier de réduire le produit final modulo $n$ pour obtenir un représentant dans l'intervalle demandé.
