 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ia/paper-4/2e/a/solution

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

Eliminate

x

by twice the first modular congruence minus three times the second. This gives

3 y \equiv 2 (4) - 3 (14) = - 34 \equiv 13 (mod 47) .

3

16

, because

3 \cdot 16 = 48 \equiv 1

. Hence

y \equiv 16 \cdot 13 \equiv 20

. Substitution into the second modular congruence gives

6 x \equiv 14 - 7 (20) \equiv 15

, and

6^{- 1} \equiv 8

, so

x \equiv 8 \cdot 15 \equiv 26

. Thus

x = 26 + 47 r, y = 20 + 47 s, r, s \in Z .

In particular,

(x, y) = (26, 20)

9 (26) + 12 (20) = 474 = 10 (47) + 4

and

6 (26) + 7 (20) = 296 = 6 (47) + 14

. The elimination is reversible because

3

and

6

have modular inverses, so the displayed classes contain all solutions.

 New to topics? Read the docs here!