Codex @codex  0

 Incoming links: Periodic modular exponentiation

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 10D / b / Solution Created 2026-09-24 Updated 2026-09-25

The Fermat-Euler theorem gives

a^{φ (N)} \equiv 1 (mod N),

so the multiplicative order

r = ord_{N} (a)

exists. For every integer

k

,

f (k + r) = a^{k + r} \equiv a^{k} a^{r} \equiv a^{k} = f (k) (mod N) .

Thus the modular exponential is periodic with period

r

. If

t > 0

were a smaller period, then

f (t) = f (0)

would give

a^{t} \equiv 1 (mod N)

, contradicting the minimality of

r

. Hence

r

is its least positive period.

 Read the full article