= Multiplicative order
{title2=$\operatorname{ord}_n(a)$}
{wiki}
For <coprime integers> $a,n$ with $n>1$, the <multiplicative order> is the least <positive integer> $d$ such that
$$
d=\operatorname{ord}_n(a),\qquad a^d\equiv1\pmod n.
$$
It counts the distinct powers in the <cyclic subgroup> generated by the <congruence class> of $a$. Thus it is an <order of a group element> in the <unit group> $(\mathbb Z/n\mathbb Z)^\times$.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[pp. 153 and 156–157, Theorem 6.29]{ref}
For example, the <modular exponentiation> $2^k\bmod7$, starting at $k=0$, produces $1,2,4,1,2,4,\ldots$. The first return to one takes three steps, so $\operatorname{ord}_7(2)=3$. Starting at the <congruence class> three and repeatedly multiplying by two instead gives $3,6,5,3,\ldots$: these are the other three <units> modulo seven, outside the <cyclic subgroup> generated by two.
\Image[/modular-power-orbits-modulo-seven.png]
{title=Multiplication by two modulo seven has two cycles; its powers follow the cycle through one}
<Euler's theorem> guarantees a return to one at exponent $\varphi(n)$, where $\varphi$ is <Euler's totient function>. Thus the <multiplicative order> exists for every <unit>.<Euler’s Theorem by Keith Conrad>[p. 1, Theorem 1.2; pp. 2–3, permutation of the units and cancellation]{ref} In fact,
$$
\operatorname{ord}_n(a)\mid\varphi(n).
$$
By <Lagrange's theorem>, the size of the <cyclic subgroup> divides the size of the <unit group>, which is <Euler's totient function>. For two modulo seven, this is $3\mid6$; the <multiplicative order> need not equal <Euler's totient function>. If $a\equiv1\pmod n$, its <multiplicative order> is one.
The <coprime integers> hypothesis is necessary: if $a^d=1+kn$, any common <divisor> of $a$ and $n$ divides one. For instance, powers of two modulo eight give $1,2,4,0,0,\ldots$, with no positive-exponent return to one. This <sequence> eventually settles, but two has no <multiplicative order> modulo eight.
Back to article page
