Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 1G / a

Solution

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$ .

There are no discussions about this article yet.

There are currently no matching articles.