Inverse modulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif a pour la multiplication modulo n est un entier u satisfaisant l'équation :

au\equiv1\pmod n.

En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤn. Une fois ainsi défini, u peut être noté a^{-1}, étant entendu implicitement que l'inversion est modulaire et se fait modulo n.

La définition est donc équivalente à :

u\equiv a^{-1}\pmod n.

L'inverse de a modulo n existe si et seulement si a et n sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par a modulo n équivaut à la multiplication par son inverse.

Définition équivalente[modifier | modifier le code]

D'après la définition ci-dessus, u est un inverse de a modulo n s'il existe un entier v tel que

1-au=nv

ou encore : tel que

au+nv=1.

Existence et unicité[modifier | modifier le code]

Vu ce qui précède, a possède un inverse modulo n si et seulement s'il existe deux entiers u et v tels que au + nv = 1. D'après le théorème de Bachet-Bézout, ceci a lieu si et seulement si PGCD(a, n) = 1, c'est-à-dire si a et n sont premiers entre eux.

De plus, si un tel inverse existe alors il est unique (modulo n) et peut se calculer grâce à l'algorithme d'Euclide étendu ou au théorème d'Euler : cf. section « Méthodes de calcul » ci-dessous.

Exemple[modifier | modifier le code]

Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11.

u\equiv3^{-1}\pmod{11}.

Cela revient à calculer u vérifiant

3u\equiv1\pmod{11}.

Dans l'ensemble de ℤ11, une solution est 4 car

3\times4=12\equiv1\pmod{11},

et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4.

À partir du moment où l'on a trouvé l'inverse de 3 dans ℤ11, on peut trouver une infinité d'autres entiers u qui satisfont aussi cette congruence. Il suffit d'ajouter des multiples de n = 11 à l'inverse que nous avons trouvé. Autrement dit, les solutions sont

u=4+11k,\quad k\in\Z,

c'est-à-dire les éléments de {…, –18, –7, 4, 15, 26, …}.

Méthodes de calcul[modifier | modifier le code]

Algorithme d'Euclide étendu[modifier | modifier le code]

L'algorithme d'Euclide étendu permet génériquement de trouver des solutions à l'identité de Bézout.

au+bv=\text{PGCD}(a, b)\,

a, b sont connus et u, v et PGCD(ab) sont des nombres recherchés.

Comme vu plus haut, l'inverse modulaire u est solution de

au+nv=1,

a et n sont connus et v un entier qui sera éliminé. On se conforme ici à la forme que l'algorithme d'Euclide étendu résout, à la différence près que PGCD(an) = 1 est d'ores et déjà connu et non à calculer.

La complexité de l'algorithme est en O(log2(n)) quand |a| < n.

Théorème d'Euler[modifier | modifier le code]

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Question book-4.svg
Cette section ne cite pas suffisamment ses sources (indiquez la date de pose grâce au paramètre date).
Pour l'améliorer, ajoutez des références vérifiables [Comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Cette méthode est une alternative à l'algorithme d'Euclide : on peut utiliser le théorème d'Euler pour calculer l'inverse modulaire[1].

Selon ce théorème, si a est premier avec n, c'est-à-dire si PGCD(a, n) = 1, alors

a^{\varphi(n)} \equiv 1 \pmod{n}

où φ(n) est l'indicatrice d'Euler. Cela résulte du fait que a appartient au groupe des unités (ℤ/nℤ)* si et seulement si a est premier avec n. L'inverse modulaire est donc donné directement par

a^{-1}\equiv a^{\varphi(n)-1}\pmod n.

Dans le cas particulier où n est premier, l'équation ci-dessus devient :

a^{-1}\equiv a^{n-2}\pmod n.

Cette méthode de calcul, généralement plus lente que l'algorithme d'Euclide, est parfois utilisée[réf. nécessaire] quand on possède une implémentation de l'exponentiation modulaire. Elle demande cependant :

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Modular multiplicative inverse » (voir la liste des auteurs).

  1. (en) Thomas Koshy, Elementary number theory with applications, 2e éd. (ISBN 978-0-12-372487-8, lire en ligne), p. 346

Articles connexes[modifier | modifier le code]