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

Table of contents
- Solution 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) .

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version