 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/10d/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

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

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.

 New to topics? Read the docs here!