Qu'est-ce que l'inverse multiplicatif modulo m ?
L'inverse multiplicatif modulaire d'un entier a modulo m est un entier x compris entre 1 et m−1 vérifiant \((a \cdot x) \bmod m = 1\). Autrement dit, lorsqu'on multiplie a par x puis qu'on divise par m, le reste vaut exactement 1. C'est l'équivalent de la division par a en arithmétique modulaire, et l'un des piliers de la théorie des nombres et de la cryptographie (génération des clés RSA, hachage, théorème des restes chinois, etc.).
Comment utiliser ce calculateur
Saisissez l'entier a et le module m (m doit être supérieur ou égal à 2). Le calculateur réduit a modulo m, applique l'algorithme d'Euclide étendu et renvoie l'inverse s'il existe. Les valeurs négatives de a sont gérées automatiquement : elles sont ramenées dans l'intervalle 0 à m−1.
La formule expliquée
Un inverse existe si et seulement si pgcd(a, m) = 1 — c'est-à-dire que a et m n'ont aucun diviseur commun autre que 1 (ils sont premiers entre eux).
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$
L'algorithme d'Euclide étendu détermine des entiers s et t tels que \(a \cdot s + m \cdot t = \gcd(a, m)\). Lorsque le pgcd vaut 1, le coefficient s réduit modulo m correspond à l'inverse. Si pgcd(a, m) ≠ 1, aucun inverse n'existe.
Exemple résolu
Cherchons l'inverse de 3 modulo 11. Il nous faut x tel que \((3 \cdot x) \bmod 11 = 1\). En testant, $$3 \cdot 4 = 12, \quad 12 \bmod 11 = 1.$$ L'inverse est donc 4. L'algorithme d'Euclide étendu donne le même résultat instantanément, puisque \(\gcd(3, 11) = 1\).
FAQ
Quand l'inverse n'existe-t-il pas ? Lorsque a et m ne sont pas premiers entre eux. Par exemple, 4 n'a pas d'inverse modulo 8, car \(\gcd(4, 8) = 4 \neq 1\).
Le module doit-il être un nombre premier ? Non. N'importe quel module convient, du moment que a lui est premier. Si m est premier, alors tout a non nul compris entre 1 et m−1 possède un inverse.
Pourquoi le résultat est-il toujours compris entre 1 et m−1 ? Parce que l'on réduit l'inverse modulo m afin d'obtenir le plus petit représentant positif canonique.
