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$

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

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

Exemple corrigé

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$