Multiplicative order

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

a^k ≡ 1 (mod n).

The order of a modulo n is usually written ord_n(a), or O_n(a).

Example

To determine the multiplicative order of 4 modulo 7, we compute 4² = 16 ≡ 2 (mod 7) and 4³ = 64 ≡ 1 (mod 7), so ord₇(4) = 3.

Properties

Even without knowledge that we are working in the multiplicative group of integers modulo n, 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 according to the pigeonhole principle there must be two powers, say s and t and without loss of generality s>t, such that a^s ≡ a^t (mod n). Since a and n are coprime, this implies that a has an inverse element a^-1 and we can multiply both sides of the congruence with a^-t, yielding a^s-t ≡ 1 (mod 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 Z_n; it has φ(n) elements, φ being Euler's totient function, and is denoted as U(n) or U(Z_n).

As a consequence of Lagrange's theorem, ord_n(a) always divides φ(n). If ord_n 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.

The order ord_n a also divides λ(n), a value of the Carmichael function, which is an even stronger statement than the divisibility of φ(n).

See also

• Modular arithmetic
• order (group theory)

References

• Weisstein, Eric W., "Multiplicative Order" from MathWorld.