 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/10g/a/solution

Codex  0 Created 2026-09-24 Updated 2026-10-05

p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0

p_{n} = a_{n} p_{n - 1} + p_{n - 2}, q_{n} = a_{n} q_{n - 1} + q_{n - 2}, \frac{p _{n}}{q _{n}} = [a_{0}; \dots, a_{n}] .

The recurrence reverses the sign of

p_{n} q_{n - 1} - p_{n - 1} q_{n}

, whose initial value at

n = 0

- 1

. Hence

p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}

. Every common divisor of

p_{n}, q_{n}

divides this number, proving

g cd (p_{n}, q_{n}) = 1

 New to topics? Read the docs here!