Calculateur d'inverse modulaire

Calculateur d'inverse modulaire

En croissance AI Skill PRO

Entrez le calcul

Résultats

Inverse modulaire
23
x tel que (a·x) mod m = 1
L'inverse existe Oui
pgcd(a, m) 1

Formule

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
Statistiques d'utilisation

Publicité

Signaler une erreur sur cette page

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}$$

Droite numérique enroulée autour d'un anneau de module circulaire façon horloge, où a fois x tombe sur 1
Un inverse modulaire x ramène a à 1 par multiplication, en bouclant autour du module 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.

Publicité
Organigramme plat des étapes de l'algorithme d'Euclide étendu produisant le gcd et les coefficients
L'algorithme d'Euclide étendu fournit des coefficients qui donnent l'inverse quand gcd(a, m) = 1.

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.

  1. 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.
  2. 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.
  3. 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.

Publicité

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\).

Dernière mise à jour:

Les plus populaires dans Mathématiques et statistiques

Voir toutes les calculatrices de Mathématiques et statistiques