In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that ak ≡ 1 (mod n). 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 sometimes written as ordn(a).
Example The powers of 4 modulo 7 are as follows:
4 0 = 1 = 0 × 7 + 1 ≡ 1 ( mod 7 ) 4 1 = 4 = 0 × 7 + 4 ≡ 4 ( mod 7 ) 4 2 = 16 = 2 × 7 + 2 ≡ 2 ( mod 7 ) 4 3 = 64 = 9 × 7 + 1 ≡ 1 ( mod 7 ) 4 4 = 256 = 36 × 7 + 4 ≡ 4 ( mod 7 ) 4 5 = 1024 = 146 × 7 + 2 ≡ 2 ( mod 7 ) ⋮ {\displaystyle {\begin{array}{llll}4^{0}&=1&=0\times 7+1&\equiv 1{\pmod {7}}\\4^{1}&=4&=0\times 7+4&\equiv 4{\pmod {7}}\\4^{2}&=16&=2\times 7+2&\equiv 2{\pmod {7}}\\4^{3}&=64&=9\times 7+1&\equiv 1{\pmod {7}}\\4^{4}&=256&=36\times 7+4&\equiv 4{\pmod {7}}\\4^{5}&=1024&=146\times 7+2&\equiv 2{\pmod {7}}\\\vdots \end{array}}}
The smallest positive integer k such that 4k ≡ 1 (mod 7) is 3, so the order of 4 (mod 7) is 3. Note that a 0 = 1 ≡ 1 ( mod n ) {\displaystyle a^{0}=1\equiv 1{\pmod {n}}} is trivially true for any non-zero a {\displaystyle a} , but since zero is not a positive integer, trivial solutions are not valid.
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 (mod n). Since a and n are coprime, a has an inverse element a−1 and we can multiply both sides of the congruence with a−t, yielding as−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 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, the order of a (mod n) always divides φ(n). If the order of 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 of a (mod n) also divides λ(n), a value of the Carmichael function, which is an even stronger statement than the divisibility of φ(n).
… excerpt ends here. Continue reading the full article.
