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$

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

Inverse de $3$ modulo $7$

La méthode

1
Appliquer l'algorithme d'Euclide à $(a, n)$ et noter les divisions successives.
Comment calculer le PGCD de deux entiers ?Voir
2
Remonter les étapes pour exprimer $1 = au + nv$ (relation de Bézout).
Comment exprimer le PGCD sous la forme de Bézout $au + bv$ ?Voir
3
L'inverse de $a$ modulo $n$ est $u \bmod n$ (réduire $u$ dans $\{0, 1, \ldots, n-1\}$ si nécessaire).

Pour comprendre, passons aux exercices.

Exercice d'exemple

Inverse de $3$ modulo $7$

1

Euclide : $7 = 3 \times 2 + 1$ , puis $3 = 1 \times 3 + 0$ .

2

On remonte : $1 = 7 - 3 \times 2$ , soit $3 \times (-2) + 7 \times 1 = 1$ .

3

$u = -2 \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 l'algorithme d'Euclide étendu pour obtenir au+nv=1au + nv = 1au+nv=1 (Bézout, possible car pgcd(a,n)=1\mathrm{pgcd}(a,n) = 1pgcd(a,n)=1) : l'inverse est u mod nu \bmod numodn

Pour comprendre, passons aux exercices.

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$