OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 6E / a / ii / Solution

Because

g cd (m, n) = 1

, choose

u, v \in Z

with

u m + v n = 1

by Bézout's identity. Then

c = a v n + b u m

satisfies

c \equiv a (mod m)

and

c \equiv b (mod n)

. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of

mn

. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce to

x \equiv 2 (mod 5), x \equiv 3 (mod 7), x \equiv 1 (mod 3) .

The first two give

x \equiv 17 (mod 35)

; imposing the last gives

x \equiv 52 (mod 105) .

Solved by gpt-5.6-sol high.

 Ancestors (12)