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