Calculatrice de l'Inverse Multiplicatif Modulaire

Qu'est-ce que l'inverse multiplicatif modulaire ?

L'inverse multiplicatif modulaire d'un entier a par rapport au modulo m est un entier x dans la plage [0, m-1] tel que :

Il est noté a⁻¹ (mod m) et est analogue à l'inverse multiplicatif en arithmétique ordinaire (c'est-à-dire 1/a), mais dans le monde de l'arithmétique modulaire.

Condition clé : L'inverse existe si et seulement si pgcd(a, m) = 1 — c'est-à-dire que a et m doivent être premiers entre eux.

Comment est-il calculé : Algorithme d'Euclide étendu

La méthode la plus efficace utilise l'algorithme d'Euclide étendu. Il permet de trouver les entiers x et y satisfaisant l'identité de Bézout :

Quand pgcd(a, m) = 1, prendre les deux côtés mod m donne a·x ≡ 1 (mod m), donc x est l'inverse modulaire.

Exemple : Trouver 3⁻¹ (mod 7) :

Le PGCD étendu donne : 3·(5) + 7·(-2) = 15 − 14 = 1, donc 3⁻¹ ≡ 5 (mod 7). Vérification : 3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

Applications en cryptographie et mathématiques

Foire Aux Questions