Periodic modular exponentiation (source code)

= Periodic modular exponentiation

For a <unit> $a$ <modulo> an <integer modulus> $N\geq2$, the <function> $f:\mathbb Z\to\mathbb Z/N\mathbb Z$, $f(x)=a^x$, is <periodic>. Negative exponents use the <modular multiplicative inverse> of $a$.

If $r$ is the <multiplicative order> of $a$, then
$$
f(x+r)=a^{x+r}=a^x a^r\equiv a^x\pmod N
$$
for every <integer> $x$. It is the least positive <period>: any positive period $t$ gives $a^t=f(t)=f(0)=1$, so $r\mid t$. For example, powers of two <modulo> seven repeat $1,2,4$, and $2^{-1}\equiv4$ fits the same cycle.

The <unit> hypothesis matters. Powers of two <modulo> eight start $1,2,4,0,0,\ldots$ on <nonnegative integers>; this whole sequence has no positive <period> from its starting point, and negative powers are undefined. <Euler's theorem> guarantees a return exponent for units, while the <multiplicative order> identifies the smallest one.