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

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

L'objectif

Calculer $a^{-1} \pmod{n}$ lorsque $n$ est un nombre premier et $a \not\equiv 0 \pmod{n}$ .

Le principe

Le petit théorème de Fermat affirme que si $p$ est premier et $p \nmid a$ , alors $a^{p-1} \equiv 1 \pmod{p}$ , d'où $a \cdot a^{p-2} \equiv 1 \pmod{p}$ .

La méthode

1
Vérifier que $n = p$ est premier et que $p \nmid a$ .
2
Calculer $a^{p-2} \pmod{p}$ par exponentiation rapide (décomposer l'exposant en base $2$ ).
Comment appliquer le petit théorème de Fermat ?Voir
3
L'inverse de $a$ modulo $p$ est $a^{p-2} \bmod p$ . Vérifier en calculant $a \cdot a^{p-2} \pmod p$ .

Exemple corrigé

Difficulté croissante de 1 à 4

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En appliquant le petit théorème de Fermat si nnn est premier : a−1≡an−2(modn)a^{-1} \equiv a^{n-2} \pmod{n}a−1≡an−2(modn)

Exemple corrigé

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