Inverse Modulaire
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)`.
`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'Equation et d'Inéquation
Calculateurs mathématiques