Multiplicative order
From Wikipedia, the free encyclopedia
In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with
- ak ≡ 1 (modulo n).
The order of a modulo n is usually written ordn a, or On(a).
For example, to determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 (modulo 7) and 43 ≡ 4×2 = 8 ≡ 1 (modulo 7), so ord7(4) = 3.
Without knowledge that we are working in a finite group, we can show that a actually has an order by noting that the powers of a can only take a finite number of different values modulo n, so there must be two powers, say s and t, such that as ≡ at module n. Since a and n are coprime, this implies that a|s-t| ≡ 1 modulo n.
The concept of multiplicative order is a special case of the order of group elements. The multiplicative order of a number a modulo n is the order of a in the multiplicative group whose elements are the residues modulo n of the numbers coprime to n, and whose group operation is multiplication modulo n. This is the group of units of the ring Zn; it has φ(n) elements, φ being Euler's totient function, and is denoted as U(n) or U(Zn).
As a consequence of Lagrange's theorem, ordna always divides φ(n). If ordn a is actually equal to φ(n) and therefore as large as possible, then a is called a primitive root modulo n. This means that the group U(n) is cyclic and the residue class of a generates it.
