Multiplicative order
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 [math]\displaystyle{ a^k\ \equiv\ 1 \pmod n }[/math].[1] 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 [math]\displaystyle{ \operatorname{ord}_n(a) }[/math].[2]
Example
The powers of 4 modulo 7 are as follows:
- [math]\displaystyle{ \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} }[/math]
The smallest positive integer k such that 4k ≡ 1 (mod 7) is 3, so the order of 4 (mod 7) is 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 (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).
Programming languages
- Maxima CAS : zn_order (a, n)[3]
- Rosetta Code - examples of multiplicative order in various languages[4]
See also
References
- ↑ Niven, Zuckerman & Montgomery 1991, Section 2.8 Definition 2.6
- ↑ von zur Gathen, Joachim; Gerhard, Jürgen (2013). Modern Computer Algebra (3rd ed.). Cambridge University Press. Section 18.1. ISBN 9781107039032. https://books.google.com/books?id=7fE9baKyqSEC&pg=PA517.
- ↑ Maxima 5.42.0 Manual: zn_order
- ↑ rosettacode.org - examples of multiplicative order in various languages
- Niven, Ivan; Zuckerman, Herbert S.; Montgomery, Hugh L. (1991). An Introduction to the Theory of Numbers (5th ed.). John Wiley & Sons. ISBN 0-471-62546-9.
External links
 |  |
