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$

Trouver $u \in \mathbb{Z}$ tel que $au \equiv 1 \pmod{n}$ .

L'objectif

Trouver $u \in \mathbb{Z}$ tel que $au \equiv 1 \pmod{n}$ .

Le principe

Si $\mathrm{pgcd}(a, n) = 1$ , Bézout garantit l'existence de $u, v$ avec $au + nv = 1$ ; alors $au \equiv 1 \pmod{n}$ , donc $u \bmod n$ est l'inverse de $a$ .

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, fais des exercices !

0/5 validés

Exercice d'exemple

Inverse de $3$ modulo $7$

Étape 1 —

Appliquer l'algorithme d'Euclide à

(a, n)

et noter les divisions successives.

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

Étape 2 —

Remonter les étapes pour exprimer

1 = au + nv

(relation de Bézout).

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

Étape 3 —

L'inverse de

a

modulo

n

est

u \bmod n

(réduire

u

dans

\{0, 1, \ldots, n-1\}

si nécessaire).

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

Application guidée

Inverse de $5$ modulo $12$

Application autonome 1

Inverse de $7$ modulo $11$

Application autonome 2

Inverse de $13$ modulo $20$

Application autonome 3

Inverse de $11$ modulo $30$ .

Crée ton compte gratuit pour accéder à la fiche et aux exercices

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, fais des exercices !

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$