multiplicative order

The powers of 4 modulo 7 are as follows:

: $\backslash begin\{array\}\{llll\}$

4^0 &= 1 &=0 \times 7 + 1 &\equiv 1\pmod7 \\

4^1 &= 4 &=0 \times 7 + 4 &\equiv 4\pmod7 \\

4^2 &= 16 &=2 \times 7 + 2 &\equiv 2\pmod7 \\

4^3 &= 64 &=9 \times 7 + 1 &\equiv 1\pmod7 \\

4^4 &= 256 &=36 \times 7 + 4 &\equiv 4\pmod7 \\

4^5 &= 1024 &=146 \times 7 + 2 &\equiv 2\pmod7 \\

\vdots\end{array}

The smallest positive integer k such that 4^k ≡ 1 (mod 7) is 3, so the order of 4 (mod 7) is 3.

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, a has an inverse element a⁻¹ 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, 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).

• Maxima CAS : zn_order (a, n)[http://maxima.sourceforge.net/docs/manual/maxima_29.html#zn_005forder Maxima 5.42.0 Manual: zn_order]
• Wolfram Language : MultiplicativeOrder[k, n][https://reference.wolfram.com/language/ref/MultiplicativeOrder.html Wolfram Language documentation]
• Rosetta Code - examples of multiplicative order in various languages[https://rosettacode.org/wiki/Multiplicative_order rosettacode.org - examples of multiplicative order in various languages]

• Discrete logarithm
• Modular arithmetic

{{Reflist}}

• {{Cite book |last1=Niven |first1=Ivan |author1-link=Ivan M. Niven |last2=Zuckerman |first2=Herbert S. |last3=Montgomery |first3=Hugh L. |author3-link=Hugh Lowell Montgomery |title=An Introduction to the Theory of Numbers |date=1991 |publisher=John Wiley & Sons |edition=5th |isbn=0-471-62546-9}}

• {{MathWorld |urlname=MultiplicativeOrder |title=Multiplicative Order}}

{{DEFAULTSORT:Multiplicative Order}}

Category:Modular arithmetic