 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ia/paper-4/5e/solution

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

The Euler theorem states that if

g cd (a, d) = 1

, then

a^{ϕ (d)} \equiv 1 (mod d) .

Let

r_{1}, \dots, r_{ϕ (d)}

d

a

permutes them, so

a^{ϕ (d)} r_{1} \dots r_{ϕ (d)} \equiv r_{1} \dots r_{ϕ (d)} (mod d) .

Their product is a unit and may be cancelled, proving the theorem.

 New to topics? Read the docs here!