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}$

Que ferais-tu face à un exercice de ce type ?

Inverse de $3$ modulo $7$ (premier)

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$ .

Pour comprendre, passons aux exercices.

Exercice d'exemple

Inverse de $3$ modulo $7$ (premier)

1

$7$ est premier et $7 \nmid 3$ , donc le petit théorème de Fermat s'applique.

2

$3^{7-2} = 3^5 = 243$ . Calculons : $3^2 = 9 \equiv 2$ , $3^4 \equiv 4$ , $3^5 \equiv 12 \equiv 5 \pmod{7}$ .

3

$3^{-1} \equiv 5 \pmod{7}$ . Vérification : $3 \times 5 = 15 \equiv 1 \pmod{7}$ . ✓

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment trouver l'inverse d'un entier aaa modulo nnn ?

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)

Pour comprendre, passons aux exercices.

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}$