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.
Let be coprime integers with , and let be their multiplicative order. For integers ,Negative exponents mean powers of the modular inverse of . Thus periodic modular exponentiation has smallest positive period , and are distinct congruence classes.[ref]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. pp. 156–157, Theorem 6.29; multiplicative notation on p. 153
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, gives , while gives . 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 by the modular inverse of , leaving . Apply Euclidean division to write with . Then ; minimality of the multiplicative order forces . The reverse implication follows from . The coprime integers hypothesis enables cancellation: modulo eight, , but this repetition supplies no multiplicative order for two.
Articles by others on the same topic
There are currently no matching articles.