= Order as the exact period of modular exponentiation
{title2=$a^x\equiv a^y\pmod n\iff\operatorname{ord}_n(a)\mid x-y$}
Let $a,n$ be <coprime integers> with $n>1$, and let $d=\operatorname{ord}_n(a)$ be their <multiplicative order>. For <integers> $x,y$,
$$
a^x\equiv a^y\pmod n\quad\Longleftrightarrow\quad d\mid(x-y).
$$
Negative exponents mean powers of the <modular inverse> of $a$. Thus <periodic modular exponentiation> has smallest positive <period> $d$, and $1,a,\ldots,a^{d-1}$ are distinct <congruence classes>.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[pp. 156–157, Theorem 6.29; multiplicative notation on p. 153]{ref}
This lets a huge <modular exponentiation> reuse a short list: reduce its exponent modulo the <multiplicative order>, then look up the corresponding power. For example, $1000\equiv1\pmod3$ gives $2^{1000}\equiv2\pmod7$, while $1001\equiv2\pmod3$ gives $2^{1001}\equiv4\pmod7$. When the <multiplicative order> is unknown, <Euler's theorem> permits reduction modulo <Euler's totient function>, though that <period> may be longer. <Repeated squaring> remains useful when computing either the unreduced or the reduced power.
For a proof outline, multiply $a^x\equiv a^y$ by the <modular inverse> of $a^y$, leaving $a^{x-y}\equiv1$. Apply <Euclidean division> to write $x-y=td+r$ with $0\leq r<d$. Then $a^{x-y}\equiv a^r$; minimality of the <multiplicative order> forces $r=0$. The reverse implication follows from $a^d\equiv1$. The <coprime integers> hypothesis enables cancellation: modulo eight, $2^3\equiv2^4\equiv0$, but this repetition supplies no <multiplicative order> for two.
Back to article page
