Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Théorème d'Euler

Important : tout ou partie de cet article est soumis à un désaccord de pertinence. Son contenu doit être considéré avec précaution jusqu'à disparition de cet avertissement. Pour toute information complémentaire sur les points remis en cause, consulter la page de discussion associée.

Le théorème d'Euler de n (φ(n) → parfois appelée indicateur d'Euler de n) est le nombre d'éléments (le cardinal) de l'ensemble restreint des résidus modulo n. φ(n) est le nombre d'entiers positifs plus petits que n et premiers par rapport à n.
Si n est premier, alors φ(n)=n-1.
Si pgcd(a,n)=1 => a^φ(n) mod n = 1

a^-1 => x=a^φ(n)-1 mod n

Par exemple quel est l'inverse de 5 modulo 7 ?
Comme 7 est premier φ(7)=7-1=6
Ainsi, l'inverse de 5 modulo 7 est :
5^6-1 mod 7=5⁵ mod 7=3.
Les 2 méthodes de calcul d'inverses peuvent être étendues pour calculer x dans l'équation :
(si pgcd(a,n)=1):

(a.x) mod n = b

Par la généralisation d'Euler on a :

x=(b×a^φ(n)-1) mod n

Par l'algorithme d'Euclide on a :

x=[b×(a^-1 mod n)] mod n

Voir aussi

• Petit théorème de Fermat