Résoudre $ax \equiv b \;[n]$ lorsque $a \wedge n = 1$ : méthode (MPSI)

1. Déterminer un inverse $u$ de $a$ modulo $n$ par l'algorithme d'Euclide étendu ($au + nv = 1$).
2. Multiplier par $u$ : $ax \equiv b \;[n] \iff x \equiv ub \;[n]$ (l'équivalence vient de ce que l'on peut remultiplier par $a$).
3. Donner les solutions sous la forme $x = x_0 + kn$, $k \in \mathbb{Z}$.

Exemple : $7x \equiv 3 \;[26]$. Euclide : $26 = 3 \times 7 + 5$, $7 = 1 \times 5 + 2$, $5 = 2 \times 2 + 1$. En remontant : $1 = 5 - 2 \times 2 = 3 \times 5 - 2 \times 7 = 3 \times 26 - 11 \times 7$. Donc $7 \times (-11) \equiv 1 \;[26]$, et l'inverse de $7$ est $-11 \equiv 15 \;[26]$ (vérification : $7 \times 15 = 105 = 4 \times 26 + 1$). Alors $x \equiv 15 \times 3 = 45 \equiv 19 \;[26]$. Vérification : $7 \times 19 = 133 = 5 \times 26 + 3$. Les solutions sont les $x = 19 + 26k$, $k \in \mathbb{Z}$.