Qu'est-ce qu'un inverse modulaire ?
L'inverse multiplicatif modulaire d'un entier a modulo m est un entier x qui vérifie \((a \cdot x) \bmod m = 1\). C'est l'équivalent de la « division » en arithmétique modulaire, et il occupe une place centrale en théorie des nombres, dans le cryptosystème RSA et dans de nombreux algorithmes de la théorie des codes. Ce calculateur détermine x à l'aide de l'algorithme d'Euclide étendu.
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
Comment utiliser ce calculateur
Saisissez le nombre a et le module m (avec \(m \geq 2\)). L'outil renvoie le plus petit inverse positif x dans l'intervalle \(0 \leq x < m\), indique si un inverse existe et affiche le \(\text{pgcd}(a, m)\). Si \(\text{pgcd}(a, m) \neq 1\), aucun inverse n'existe et le résultat affiché est « Aucun ».
La formule expliquée
Un inverse n'existe que lorsque \(\text{pgcd}(a, m) = 1\), autrement dit lorsque a et m sont premiers entre eux. L'algorithme d'Euclide étendu trouve des entiers x et y vérifiant \(a \cdot x + m \cdot y = \text{pgcd}(a, m)\). Quand le pgcd vaut 1, la réduction de x modulo m donne l'inverse. Le résultat est ramené à une valeur positive en lui ajoutant m s'il est négatif.
Exemple détaillé
Cherchons l'inverse de 3 modulo 11. Il nous faut un x tel que \(3x \equiv 1 \pmod{11}\). En essayant, $$3 \times 4 = 12 = 11 + 1,$$ donc \(12 \bmod 11 = 1\). Par conséquent x = 4. L'algorithme d'Euclide étendu renvoie la même valeur, et \(\text{pgcd}(3, 11) = 1\), ce qui confirme l'existence de l'inverse.
FAQ
Quand n'existe-t-il aucun inverse ? Lorsque a et m ont un facteur commun supérieur à 1 — par exemple 4 modulo 6 (\(\text{pgcd} = 2\)) n'admet pas d'inverse.
m doit-il être premier ? Non. m peut être n'importe quel entier \(\geq 2\) ; seul compte le fait que a et m soient premiers entre eux.
Dans quel intervalle se situe la réponse ? L'inverse est donné comme le plus petit résidu positif, compris entre 0 et \(m - 1\).
