Étape 1
Pour déterminer l'entier $x$ vérifiant $19x \equiv 7 \pmod{53}$, cherchons d'abord un inverse de $19$ modulo $53$.
Étape 2
Appliquons l'algorithme d'Euclide pour calculer le plus grand commun diviseur de $53$ et $19$ :
Étape 3
$$53 = 2 \times 19 + 15$$
Étape 4
$$19 = 1 \times 15 + 4$$
Étape 5
$$15 = 3 \times 4 + 3$$
Étape 6
$$4 = 1 \times 3 + 1$$
Étape 7
Le dernier reste non nul est $1$, donc $\text{PGCD}(53, 19) = 1$. Les nombres $19$ et $53$ sont premiers entre eux.
Étape 8
Exprimons $1$ en remontant les égalités de l'algorithme d'Euclide :
Étape 9
$$1 = 4 - 1 \times 3$$
Étape 10
$$1 = 4 - (15 - 3 \times 4) = 4 \times 4 - 15$$
Étape 11
$$1 = 4 \times (19 - 15) - 15 = 4 \times 19 - 5 \times 15$$
Étape 12
$$1 = 4 \times 19 - 5 \times (53 - 2 \times 19) = 14 \times 19 - 5 \times 53$$
Étape 13
On obtient l'égalité $14 \times 19 - 5 \times 53 = 1$. En passant modulo $53$, cette relation devient $14 \times 19 \equiv 1 \pmod{53}$. Ainsi, $14$ est un inverse de $19$ modulo $53$.
Étape 14
Multiplions chaque membre de la congruence initiale $19x \equiv 7 \pmod{53}$ par $14$ :
Étape 15
$$(14 \times 19) x \equiv 14 \times 7 \pmod{53}$$
Étape 16
Comme $14 \times 19 \equiv 1 \pmod{53}$ et $14 \times 7 = 98$, la congruence se simplifie en $x \equiv 98 \pmod{53}$.
Étape 17
Effectuons la division euclidienne de $98$ par $53$ : $98 = 1 \times 53 + 45$. On en déduit que $98 \equiv 45 \pmod{53}$.
Étape 18
L'unique entier $x$ compris entre $0$ et $52$ vérifiant cette congruence est $45$.
Méthode clé
Pour résoudre $a x \equiv b \pmod n$, on cherche d'abord un entier $u$ tel que $a u \equiv 1 \pmod n$ grâce à l'algorithme d'Euclide et l'identité de Bézout, puis on multiplie la congruence par $u$.
Piège à éviter
Attention : on ne peut pas diviser une congruence par un entier. Il faut obligatoirement multiplier par son inverse modulaire.
