 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ia/paper-4/6e/a/i/solution

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

The Euclidean algorithm repeatedly replaces a pair

(a, b)

(b, a - q b)

without changing its greatest common divisor. Reversing the divisions expresses

g cd (a, b)

α a + β b

Here

3 = 3 (15) - 2 (21)

, and therefore

1 = 12 \cdot 3 - 35 = 36 (15) - 24 (21) - 35.

One solution is

(x, y, z) = (36, - 24, - 1)

. It is not unique: for every

t \in Z

(x, y, z) = (36 + 7 t, - 24 - 5 t, - 1)

is another solution.

 New to topics? Read the docs here!