 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/1g/a/solution

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

m_{1}, \dots, m_{r}

, put

M = \prod_{i} m_{i}

. The Chinese remainder theorem states that reduction gives an isomorphism

Z / M Z ⟶ \prod_{i = 1}^{r} Z / m_{i} Z .

Equivalently, every system

x \equiv a_{i} (mod m_{i})

has one solution modulo

M

For existence, let

M_{i} = M / m_{i}

. Since

g cd (M_{i}, m_{i}) = 1

, choose

u_{i}

with

u_{i} M_{i} \equiv 1 (mod m_{i})

. Then

x = \sum_{i = 1}^{r} a_{i} u_{i} M_{i}

has every required residue: modulo

m_{j}

, all terms except the

j

th vanish and the remaining term is

a_{j}

. For uniqueness, if

x

and

y

have the same residues, every

m_{i}

divides

x - y

. Pairwise coprimality then makes

M

divide

x - y

. Thus the simultaneous solution exists and is unique modulo $M$ .

 New to topics? Read the docs here!