Comment trouver l'inverse d'un entier $a$ modulo $n$ ?

En appliquant l'algorithme d'Euclide étendu pour obtenir $au + nv = 1$ (Bézout, possible car $\mathrm{pgcd}(a,n) = 1$) : l'inverse est $u \bmod n$

Calcul de l'inverse de $a$ modulo $n$ par l'algorithme d'Euclide étendu et la relation de Bézout.

En appliquant le petit théorème de Fermat si $n$ est premier : $a^{-1} \equiv a^{n-2} \pmod{n}$

Calcul de l'inverse modulaire par exponentiation rapide lorsque le modulo est un nombre premier.