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 $a^k\ \equiv\ 1 \pmod 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 $\operatorname_n(a)$.

Example

The powers of 4 modulo 7 are as follows:

: $\begin 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$

The smallest positive integer ''k'' such that 4^''k'' ≡ 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 ''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'').

Programming languages

* Maxima CAS : zn_order (a, n)
* Rosetta Code - examples of multiplicative order in various languagesrosettacode.org - examples of multiplicative order in various languages
/ref>

See also

* Discrete logarithm
* Modular arithmetic

References

*

External links

*

{{DEFAULTSORT:Multiplicative Order
Modular arithmetic