- Ordre multiplicatif
-
En mathématiques et plus précisément en arithmétique modulaire, soit un entier relatif a et un entier naturel n avec pgcd(a,n) = 1, l'ordre multiplicatif de a modulo n est le plus petit entier k > 0 tel que
- ak ≡ 1 (modulo n).
L'ordre de a modulo n est écrit généralement ordn a, ou On(a).
Par exemple, pour déterminer l'ordre multiplicatif de 4 modulo 7, nous calculons 42 = 16 ≡ 2 (modulo 7) et 43 ≡ 4×2 = 8 ≡ 1 (modulo 7), donc ord7(4) = 3.
De façon équivalente, l'ordre multiplicatif de a modulo n est l'ordre du résidu de a modulo n, dans le groupe multiplicatif U(n) des unités de l'anneau Z/nZ. Les éléments de ce groupe sont les résidus modulo n des nombres premiers à n, et il y en a φ(n), φ étant la fonction indicatrice d'Euler.
D'après le théorème de Lagrange, ordna divise donc φ(n), et lui est égal si et seulement le groupe U(n) est cyclique et engendré par le résidu de a. Ce résidu est alors appelé une racine primitive modulo n.
Il existe des racines primitives modulo n si et seulement si U(n) est cyclique, et dans ce cas, il en existe φ(φ(n)). Par exemple, si p est un nombre premier, U(p) est cyclique d'ordre φ(p) = p - 1, donc il existe φ(p - 1) racines primitives modulo p.
Référence
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Multiplicative order » (voir la liste des auteurs)
Voir aussi
Wikimedia Foundation. 2010.
