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.