Terminale › Arithmétique › Inverse modulo n
Inverse modulo n : énoncé (Maths expertes)
Propriété
Inverse modulo n
Soit $n \geqslant 2$ et $a \in \mathbb{Z}$. Il existe un entier $a'$ tel que $aa' \equiv 1 \;[n]$ si et seulement si $a$ et $n$ sont premiers entre eux. On dit que $a'$ est un inverse de $a$ modulo $n$.
Preuve. $aa' \equiv 1 \;[n]$ équivaut à l'existence de $k \in \mathbb{Z}$ tel que $aa' - 1 = kn$, c'est-à-dire $aa' + n(-k) = 1$. Par le théorème de Bézout, un tel couple existe si et seulement si $\mathrm{PGCD}(a, n) = 1$.
Exemple
Résoudre 3x ≡ 4 [7]
$3 \times 5 = 15 \equiv 1 \;[7]$, donc $5$ est un inverse de $3$ modulo $7$.
- Si $3x \equiv 4 \;[7]$, en multipliant par $5$ : $15x \equiv 20 \;[7]$, soit $x \equiv 6 \;[7]$.
- Réciproquement, si $x \equiv 6 \;[7]$, alors $3x \equiv 18 \equiv 4 \;[7]$.
Les solutions sont les entiers $x = 6 + 7k$, $k \in \mathbb{Z}$.
S’entraîner
- Reste d'une grande puissance
- Une équation de congruence
- Carrés modulo 8 et sommes de trois carrés
- Nombres de Mersenne
- Deux congruences simultanées