Periodic modular exponentiation

For a unit $a$ modulo $N$, the function $x\mapsto a^x\mathrm{mod}N$ is periodic on the integers.

Let $a,n$ be coprime integers with $n>1$, and let $d={\mathrm{ord}}_n(a)$ be their multiplicative order. For integers $x,y$,Negative exponents mean powers of the modular inverse of $a$. Thus periodic modular exponentiation has smallest positive period $d$, and $1,a,\dots ,a^{d-1}$ are distinct congruence classes.^[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\equiv 1(\mathrm{mod}3)$ gives $2^{1000}\equiv 2(\mathrm{mod}7)$, while $1001\equiv 2(\mathrm{mod}3)$ gives $2^{1001}\equiv 4(\mathrm{mod}7)$. 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}\equiv 1$. Apply Euclidean division to write $x-y=td+r$ with $0\le r<d$. Then $a^{x-y}\equiv a^r$; minimality of the multiplicative order forces $r=0$. The reverse implication follows from $a^d\equiv 1$. The coprime integers hypothesis enables cancellation: modulo eight, $2^3\equiv 2^4\equiv 0$, but this repetition supplies no multiplicative order for two.