# PowerMod Is Eventually Periodic

PowerMod Is Eventually Periodic

The sequence =(modp) is known to be eventually periodic, which is to say that there is a smallest positive such that = for all . Naturally we call the period, and the minimal value of , the periodicity onset. L. Euler proved that the period must divide the totient of the modulus .

c

n

n

a

T

c

n+T

c

n

n≥

n

0

T

n

0

ϕ(p)

In case of coprime and , the onset is zero.

a

p

n

0