Periodic modular exponentiation
ID: periodic-modular-exponentiation
For a unit modulo an integer modulus , the function , , is periodic. Negative exponents use the modular multiplicative inverse of .
If is the multiplicative order of , thenfor every integer . It is the least positive period: any positive period gives , so . For example, powers of two modulo seven repeat , and fits the same cycle.
The unit hypothesis matters. Powers of two modulo eight start 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.
New to topics? Read the docs here!