WOLFRAM|DEMONSTRATIONS PROJECT

PowerMod Is Eventually Periodic

​
a
14
p
24
GCD(a, p) = 2
period = 2
periodicity onset = 3
ϕ(p) = 8
The sequence
c
n
=
n
a
(modp)
is known to be eventually periodic, which is to say that there is a smallest positive
T
such that
c
n+T
=
c
n
for all
n≥
n
0
. Naturally we call
T
the period, and the minimal value of
n
0
, the periodicity onset. L. Euler proved that the period must divide the totient of the modulus
ϕ(p)
.
In case of coprime
a
and
p
, the onset
n
0
is zero.