Inverse Modulaire

Calcul de x, l'inverse de a modulo n,   ax`\equiv`1 (mod n).


Avez-vous des suggestions pour améliorer cette page ?

L'inverse modulaire : définition et existence

a et n sont deux nombres entiers.
L'inverse modulaire de a modulo n est l'entier x tel que,

`a * x \equiv 1 (mod n)`

x est parfois noté `a^(-1)`.

Ce qui est équivalent au fait qu'il existe un entier k tel que,

`1 - a * x = k*n`

`a * x + k*n = 1`

D'après le Théorème de Bezout, k existe si et seulement a et n sont premiers entre eux.

En conclusion, l'inverse modulaire existe si et seulement si a et n sont premiers entre eux. Il est alors unique (modulo n) c'est à dire qu'il en existe un seul compris entre 1 et n mais on peut en trouver une infinité si l'on ajoute des multiples de n à x car quelque soit l'entier p alors,

`a * (x+p*n) \equiv 1 (mod n)`

Comment calculer l'inverse modulaire ?

L'inverse modulaire peut être calculé en utilisant l'algorithme d'Euclide étendu.
A l'aide de cet algorithme, si a et n sont premiers entre eux, on trouve des coefficients u et v deux entiers tels que,

`u*a + v*n = 1`

En appliquant modulo n aux membres de cette égalité, on obtient,

`u*a \equiv 1 (mod n)`

On déduit que l'inverse de a modulo n est le coefficient de a trouvé grâce à l'algorithme d'Euclide étendu.

Voir aussi

Test de nombres premiers entre eux
Calculateur de PGCD
Théorème de Bezout et Algorithme d'Euclide étendu
Calculateurs d'arithmétique
Calculateurs d'équation
Calculateurs mathématiques