Chinese remainder theorem

By Ryan Ng

Suppose we want to find x such that:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

The Chinese remainder theorem works off a very simple observation. If I have a multiple of 3 × 5 = 15, it will be 0 mod 3 and mod 5. The same is true for 5 × 7 and 3 × 7. So if we write this as a linear combination:

x = 3 × 5 × a + 5 × 7 × b + 3 × 7 × c

then for example, if we take x mod 3, only the middle term remains.

x ≡ 5 × 7 × b mod 3

so we just need to solve

5 × 7 × b ≡ 2 (mod 3)

(-1) × (1) × b ≡ 2 (mod 3)

and we get b ≡ 1 (mod 3)

Doing the same for the others, we get 

3 × 5 × a ≡ 2 (mod 7)

and 

3 × 7 × c ≡ 3 (mod 5)

3 × 5 × a ≡ 3 × (-2) × a ≡ -6a ≡ a ≡ 2 (mod 7)

3 × 7 × c ≡ 3 × 2 × c ≡ 6c ≡ c ≡ 3 (mod 5)

So the smallest positive value of x, taking the smallest values of a, b, and c is 

x = 3 × 5 × (2) + 5 × 7 × (1) + 3 × 7 × (3) = 128

Try these questions

These honestly don’t need much explanation – when we use the Chinese remainder theorem, it’s usually just a direct application.

Question 1

A box contains gold coins. 

If the coins are equally divided among six friends, four coins are left over. 

If the coins are equally divided among five friends, three coins are left over.

If the box holds the smallest number of coins that meets these two conditions, how many coins are left when equally divided among seven friends?

Question 2

Find the smallest positive integer x such that x leaves remainder p - 1 upon division by p for all prime numbers less than 12. 

Question 3

Find all solutions to 

5x ≡ 25 (mod 120)

16x ≡ 20 (mod 252)

Question 4

How many numbers are there less than 2 × 3 × 5 × 7 × 11 × 13 divisible by 3, 7, and 13 and not by 2, 5 and 11?