Qu'est-ce qu'un inverse multiplicatif ?
L'inverse multiplicatif d'un nombre est la valeur par laquelle il faut le multiplier pour obtenir 1. Pour un nombre réel ordinaire a, cet inverse est tout simplement le quotient \(1/a\) — par exemple, l'inverse de 4 est 0,25 puisque \(4 \times 0{,}25 = 1\). Le zéro n'a pas d'inverse, car aucun nombre multiplié par zéro ne donne un.
L'inverse modulaire
En arithmétique modulaire, l'inverse multiplicatif de a (mod m) est l'entier x compris entre 0 et m−1 tel que \(a \cdot x \equiv 1 \pmod{m}\). On le rencontre en permanence en théorie des nombres et en cryptographie (RSA, fonctions de hachage, codes correcteurs d'erreurs). Un inverse modulaire n'existe que si a et m sont premiers entre eux, c'est-à-dire lorsque \(\gcd(a, m) = 1\). Ce calculateur le détermine à l'aide de l'algorithme d'Euclide étendu.
Comment utiliser ce calculateur
Saisissez votre nombre a. Laissez le module à 0 (ou vide) pour obtenir l'inverse classique \(1/a\). Pour calculer un inverse modulaire, indiquez un module m supérieur à 1 ; le calculateur réduit a modulo m et renvoie l'inverse, ou vous signale qu'il n'en existe aucun si a et m partagent un facteur commun.
Exemple détaillé
Cherchons l'inverse de 3 modulo 11. Il faut trouver x tel que \(3x \equiv 1 \pmod{11}\). En testant \(x = 4\), on obtient $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}.$$ L'inverse modulaire est donc 4. En tant qu'inverse classique, l'inverse de 3 est \(1/3 \approx 0{,}333333\).
Calcul d'un inverse modulaire à la main avec l'algorithme d'Euclide étendu
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 permet de le trouver.
- Exécuter l'algorithme d'Euclide sur \((m, a)\). Divisez de façon répétée, en remplaçant la paire \((m, a)\) par \((a, r)\), où \(r\) est le reste, jusqu'à ce que le reste soit 0.
- Vérifier le PGCD. Le dernier reste non nul est \(\gcd(a, m)\). S'il n'est pas égal à 1, il n'existe pas d'inverse et vous vous arrêtez.
- Remonter par substitution à travers les lignes de division pour écrire \(1 = a \cdot x + m \cdot y\).
- Réduire \(x\) modulo \(m\) dans l'intervalle de 0 à \(m-1\). Ajoutez \(m\) si \(x\) est négatif.
- Vérifier que \(a \cdot x \bmod m = 1\).
Exemple : l'inverse de 7 modulo 26.
| Ligne | Division | Quotient | Reste |
|---|---|---|---|
| 1 | 26 = 3·7 + 5 | 3 | 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, 26) = 1\) et l'inverse existe.
Remontée par substitution, à partir de la ligne 3 :
$$1 = 5 - 2\cdot 2$$
En substituant \(2 = 7 - 1\cdot 5\) issu de la ligne 2 :
$$1 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7$$
En substituant \(5 = 26 - 3\cdot 7\) issu de la ligne 1 :
$$1 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$$
Donc \(x = -11\). En réduisant, on obtient \(-11 + 26 = \)15.
Vérification : \(7 \cdot 15 = 105 = 4\cdot 26 + 1\), donc \(105 \bmod 26 = 1\). ✓
Inverse réciproque ou inverse modulaire : comparaison d'exemples
L'inverse \(1/a\) existe pour tout nombre réel non nul. L'inverse modulaire n'existe que lorsque \(a\) et \(m\) sont premiers entre eux. Ce sont deux quantités différentes.
| a | Modulo m | Réciproque 1/a | Inverse modulaire | Remarque |
|---|---|---|---|---|
| 3 | 11 | 0,3333 | 4 | 3·4 = 12 ≡ 1 (mod 11) |
| 4 | 8 | 0,25 | aucun | gcd(4, 8) = 4, et non 1 |
| 7 | 26 | 0,142857 | 15 | 7·15 = 105 ≡ 1 (mod 26) |
| −3 | 11 | −0,3333 | 7 | −3 se réduit à 8 mod 11, et 8·7 = 56 ≡ 1 (mod 11) |
| 0 | tout m > 1 | indéfinie | aucun | 0·x vaut toujours 0, jamais 1 |
La réciproque ne tient pas compte du modulo. L'inverse modulaire est un entier compris entre 0 et \(m-1\), et il n'existe que lorsque \(\gcd(a, m) = 1\).
FAQ
Pourquoi le zéro n'a-t-il pas d'inverse ? Parce que tout nombre multiplié par 0 donne 0, jamais 1.
Dans quels cas un inverse modulaire n'existe-t-il pas ? Lorsque \(\gcd(a, m) \neq 1\) — par exemple, 4 n'a pas d'inverse mod 8, car ils partagent le facteur 4.
Puis-je utiliser un nombre négatif pour l'inverse modulaire ? Oui ; il est d'abord ramené dans l'intervalle de 0 à m−1 avant l'inversion.