 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/15c/b/solution

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

f (x) = a^{x} (mod N), x \in Z,

using the inverse of

a

for negative

x

. Since

a^{r} \equiv 1

f (x + r) = f (x)

. Conversely, if

f (x) = f (y)

then

a^{x - y} \equiv 1

, so the definition of order gives

r ∣ x - y

. Two integers in the same block of

r

consecutive integers cannot differ by a nonzero multiple of

r

. Hence

f

is one-to-one within each period.

 New to topics? Read the docs here!