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.
Étape par étape : algorithme d'Euclide étendu à la main
L'inverse modulaire de a modulo m est le nombre x tel que \(a \cdot x \equiv 1 \pmod{m}\). Il n'existe que lorsque \(\gcd(a, m) = 1\). L'algorithme d'Euclide étendu le trouve en trois étapes.
- Divisions successives. Divisez m par a, puis divisez le diviseur précédent par le reste, et ainsi de suite, jusqu'à ce que le reste soit 0. Le dernier reste non nul est le PGCD. S'il n'est pas égal à 1, aucun inverse n'existe.
- Exprimer 1 comme combinaison. Procédez à rebours (substitution arrière), ou suivez les coefficients au fur et à mesure, pour écrire \(1 = a \cdot x + m \cdot y\). C'est l'identité de Bézout.
- Réduire x. Prenez \(x \bmod m\). Si x est négatif, ajoutez m (répétez si nécessaire) pour obtenir un nombre entre 0 et m − 1.
Exemple détaillé : a = 7, m = 40.
| Étape | Division | Quotient q | Reste |
|---|---|---|---|
| 1 | 40 = 5·7 + 5 | 5 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
Le dernier reste non nul est 1, donc \(\gcd(7, 40) = 1\) et un inverse existe.
Substitution arrière :
$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$
Donc \(7 \cdot (-17) + 40 \cdot 3 = 1\), ce qui donne \(x = -17\).
Vérification itérative (coefficient t de a) : partez de \(t_0 = 0\) (pour m = 40) et \(t_1 = 1\) (pour a = 7), puis utilisez \(t_{k+1} = t_{k-1} - q_k \, t_k\).
| Reste | q utilisé | t |
|---|---|---|
| 40 | – | 0 |
| 7 | – | 1 |
| 5 | 5 | 0 − 5·1 = −5 |
| 2 | 1 | 1 − 1·(−5) = 6 |
| 1 | 2 | −5 − 2·6 = −17 |
La ligne où le reste atteint 1 donne \(t = -17\). Réduisons-le : \(-17 + 40 = \)23.
Vérification : \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), donc \(161 \bmod 40 = 1\). ✓
La même méthode fonctionne pour des nombres plus grands. Pour a = 17, m = 3120, elle donne x = 2753, car \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). Ce couple est un exemple classique de manuel sur RSA.
Exemples d'entrées et leurs inverses
Chaque inverse ci-dessous vérifie \((a \cdot x) \bmod m = 1\). Lorsque \(\gcd(a, m) > 1\), aucun inverse n'existe.
| a | m | pgcd(a, m) | Inverse x | Vérification |
|---|---|---|---|---|
| 3 | 11 | 1 | 4 | 3·4 = 12 = 1·11 + 1 |
| 7 | 26 | 1 | 15 | 7·15 = 105 = 4·26 + 1 |
| 5 | 12 | 1 | 5 | 5·5 = 25 = 2·12 + 1 |
| 10 | 17 | 1 | 12 | 10·12 = 120 = 7·17 + 1 |
| 17 | 3120 | 1 | 2753 | 17·2753 = 46801 = 15·3120 + 1 |
| 4 | 6 | 2 | Aucun | 4x mod 6 est toujours pair, jamais 1 |
| 6 | 9 | 3 | Aucun | 6x mod 9 est toujours un multiple de 3, jamais 1 |
Remarquez que 5 est son propre inverse modulo 12. En général, \(x^2 \equiv 1 \pmod{m}\) possède des solutions autres que 1, donc certains nombres sont leurs propres inverses.
Termes clés : premiers entre eux, PGCD, congruence et résidu
- Module (m) : l'entier positif à partir duquel les valeurs reviennent à zéro, comme sur le cadran d'une horloge.
- Congruence (≡) : \(a \equiv b \pmod{m}\) signifie que m divise \(a - b\), donc a et b ont le même reste lorsqu'on les divise par m.
- PGCD : le plus grand commun diviseur, le plus grand entier qui divise les deux nombres.
- Premiers entre eux : deux entiers dont le PGCD est 1. C'est exactement la condition pour qu'un inverse modulaire existe.
- Identité de Bézout : pour les entiers a et m, il existe des entiers x et y tels que \(a \cdot x + m \cdot y = \gcd(a, m)\). Lorsque le PGCD vaut 1, la réduction de cette équation modulo m donne \(a \cdot x \equiv 1\), donc x est l'inverse.
- Classe de résidus : l'ensemble de tous les entiers ayant le même reste modulo m. L'inverse est unique en tant que classe de résidus, et le calculateur renvoie le représentant compris entre 0 et m − 1.
- Inverse multiplicatif modulaire : le résidu \(x = a^{-1} \bmod m\) avec \(a \cdot x \equiv 1 \pmod{m}\).
Théorème d'Euler : si \(\gcd(a, m) = 1\), alors \(a^{\varphi(m)} \equiv 1 \pmod{m}\), où \(\varphi\) est la fonction indicatrice d'Euler. Ainsi, l'inverse peut aussi être calculé comme \(a^{\varphi(m)-1} \bmod m\).
Petit théorème de Fermat : lorsque m = p est premier, \(\varphi(p) = p - 1\), donc \(a^{-1} \equiv a^{p-2} \pmod{p}\) pour tout a non divisible par p. Exemple : \(3^{9} = 19683 = 1789 \cdot 11 + 4\), donc \(3^{-1} \equiv 4 \pmod{11}\), ce qui correspond au tableau ci-dessus. La formule des puissances nécessite la factorisation de m (pour trouver \(\varphi\)), alors que l'algorithme d'Euclide étendu ne l'exige pas ; c'est donc généralement la méthode la plus rapide pour les modules quelconques.
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\).