Procédure pour trouver un entier x tel que a·x ≡ 1 (mod m) lorsqu'un tel x existe ; c'est trouver l'inverse multiplicatif de a modulo m, généralement via l'algorithme d'Euclide étendu quand pgcd(a,m)=1.

Principe

Un inverse existe modulo m exactement quand pgcd(a,m)=1. On calcule le pgcd et les coefficients de Bézout ; le coefficient associé à a, réduit modulo m, donne l'inverse.

Démonstration

Inverse de 3 modulo 11 : pgcd(3,11)=1 et 3·4 = 12 ≡ 1 (mod 11), donc l'inverse est 4. L'algorithme euclidien étendu fournit également le coefficient 4 comme solution de Bézout pour 3 et 11.

Mauvaise application

Demander un inverse quand pgcd(a,m) ≠ 1 (par exemple l'inverse de 6 modulo 9), ou employer des calculs en virgule flottante qui effacent l'information de divisibilité exacte.

Conséquence

Un inverse modulaire correct permet la division en arithmétique modulaire, la résolution de congruences linéaires et soutient des opérations cryptographiques comme la création et la vérification de signatures.

Inversion

La réversion consiste à considérer les cas sans inverse : lorsque pgcd(a,m) > 1, il peut exister plusieurs solutions à a·x ≡ b ou aucune solution unique, donc l'inversion standard n'est pas possible.

Limite

Défini seulement dans des anneaux où des inverses multiplicatifs peuvent exister ; pour Z/mZ un inverse existe si et seulement si a est premier avec m. Pour des modules composites il faut vérifier le pgcd ; dans des anneaux non commutatifs, inverses à gauche et à droite peuvent différer.

Tension sémantique

Proche du concept d'inverse multiplicatif dans un corps ; la tension vient du fait que Z/mZ n'est corps que quand m est premier, donc l'existence d'un 'inverse modulaire' pour modules composites requiert la condition de coprimalité et n'est pas automatique.

Synthèse

L'inversion modulaire combine le test du pgcd et l'extraction des coefficients de Bézout pour obtenir un entier qui sert d'inverse multiplicatif de a modulo m chaque fois que les nombres sont premiers entre eux.