Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Inverse modulaire
Résumé
En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif pour la multiplication modulo est un entier satisfaisant l'équation :
En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté Z/nZ ou Z. Une fois ainsi défini, peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo .
La définition est donc équivalente à :
L'inverse de a modulo existe si et seulement si et sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par modulo équivaut à la multiplication par son inverse.
D'après la définition ci-dessus, est un inverse de modulo s'il existe un entier tel que
ou encore : tel que
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 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.
Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11.
Cela revient à calculer u vérifiant
Dans l'ensemble de Z, une solution est 4 car
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 Z, 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
c'est-à-dire les éléments de {..., –18, –7, 4, 15, 26, ...}.
L'algorithme d'Euclide étendu permet génériquement de trouver des solutions à l'identité de Bézout.
où a, b sont connus et u, v et PGCD(a, b) sont des nombres recherchés.
Comme vu plus haut, l'inverse modulaire est solution de
où a et n sont connus et v un entier qui sera éliminé.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.