Pour un entier a premier à N, l'ordre multiplicatif est le plus petit entier positif k tel que a^k ≡ 1 (mod N) ; c'est l'ordre de a dans le groupe (Z/NZ)^×.

Principe

L'ordre de a divise φ(N) et organise le sous-groupe cyclique engendré par a ; les ordres déterminent la périodicité des puissances et le domaine des logarithmes discrets.

Démonstration

Avec a = 3 et N = 7 : 3^1≡3, 3^2≡2, 3^3≡6, 3^4≡4, 3^5≡5, 3^6≡1 (mod 7), donc l'ordre multiplicatif de 3 modulo 7 est 6.

Mauvaise application

Supposer l'existence d'un ordre pour un a non premier à N ou confondre ordre multiplicatif et ordre additif conduit à des inférences algébriques incorrectes.

Conséquence

Connaître l'ordre de a donne la taille du sous-groupe cyclique qu'il engendre, indique quels exposants produisent un résidu donné et contraint les solutions d'équations congruentes comme a^x ≡ b (mod N).

Inversion

L'inversion donne des éléments d'ordre 1 (l'identité) ou d'ordre très petit qui engendrent des sous-groupes triviaux ou minuscules plutôt que des cycles complets ; des éléments d'ordre divisant un facteur propre de φ(N) ne peuvent pas engendrer toutes les unités.

Limite

Défini seulement pour a avec gcd(a,N)=1 ; l'ordre est fini et divise φ(N). Il ne s'applique pas aux diviseurs de zéro ni aux bases non entières sauf si l'on généralise la structure des unités.

Tension sémantique

Il faut distinguer l'ordre multiplicatif modulo N de la notion d'ordre multiplicatif dans d'autres structures algébriques (par ex. matrices), où l'ordre est la plus petite puissance positive donnant l'identité dans cette structure.

Synthèse

L'ordre multiplicatif modulo N mesure combien de multiplications par a sont nécessaires pour revenir à 1 modulo N, codant la structure du sous-groupe cyclique engendré par a parmi les unités modulo N.