Multiplicative order


In number theory, given an integer a and a positive integer n coprime to a, the multiplicative order of a modulo n is the smallest positive integer k with
In other words, the multiplicative order of a modulo n is the order of a in the multiplicative group of the units in the ring of the integers modulo n.
The order of a modulo n is usually written as or

Example

The powers of 4 modulo 7 are as follows:
The smallest positive integer k such that 4k = 1 is 3, so O7 = 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 as ≡ at . 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 as−t ≡ 1 .
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 φ elements, φ being Euler's totient function, and is denoted as U or U.
As a consequence of Lagrange's theorem, ordn always divides φ. If ordn is actually equal to φ, and therefore as large as possible, then a is called a primitive root modulo n. This means that the group U is cyclic and the residue class of a generates it.
The order ordn a also divides λ, a value of the Carmichael function, which is an even stronger statement than the divisibility of φ.

Programming languages