Inverse modulo $n$ : énoncé (MPSI)

Soient $n \geqslant 2$ et $a \in \mathbb{Z}$. Il existe $u \in \mathbb{Z}$ tel que $au \equiv 1 \;[n]$ si et seulement si $a \wedge n = 1$. Un tel $u$ est appelé inverse de $a$ modulo $n$.

Preuve. $au \equiv 1 \;[n]$ équivaut à l'existence de $k \in \mathbb{Z}$ tel que $au - 1 = kn$, c'est-à-dire $au + n(-k) = 1$. Par le théorème de Bézout, un tel couple existe si et seulement si $a \wedge n = 1$.

En particulier, si $p$ est premier, tout entier non divisible par $p$ est inversible modulo $p$.