Inverse modulaire

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif pour la multiplication modulo est un entier satisfaisant l'équation : En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté Z/nZ ou Z. Une fois ainsi défini, peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo . La définition est donc équivalente à : L'inverse de a modulo existe si et seulement si et sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par modulo équivaut à la multiplication par son inverse. D'après la définition ci-dessus, est un inverse de modulo s'il existe un entier tel que ou encore : tel que Vu ce qui précède, a possède un inverse modulo n si et seulement s'il existe deux entiers u et v tels que au + nv = 1. D'après le théorème de Bachet-Bézout, ceci a lieu si et seulement si c'est-à-dire si a et n sont premiers entre eux. De plus, si un tel inverse existe alors il est unique (modulo n) et peut se calculer grâce à l'algorithme d'Euclide étendu ou au théorème d'Euler : cf. section « Méthodes de calcul » ci-dessous. Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11. Cela revient à calculer u vérifiant Dans l'ensemble de Z, une solution est 4 car et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4. À partir du moment où l'on a trouvé l'inverse de 3 dans Z, on peut trouver une infinité d'autres entiers u qui satisfont aussi cette congruence. Il suffit d'ajouter des multiples de n = 11 à l'inverse que nous avons trouvé. Autrement dit, les solutions sont c'est-à-dire les éléments de {..., –18, –7, 4, 15, 26, ...}. L'algorithme d'Euclide étendu permet génériquement de trouver des solutions à l'identité de Bézout. où a, b sont connus et u, v et PGCD(a, b) sont des nombres recherchés. Comme vu plus haut, l'inverse modulaire est solution de où a et n sont connus et v un entier qui sera éliminé.