The Chinese Remainder Theorem

The Chinese Remainder Theorem is a method to solve the following puzzle, posed by Sun Zi around the 4th Century AD.

What number has a remainder of 2 when divided by 3, a remainder of 3 when divided by 5 and a remainder of 2 when divided by 7?

There are a couple of methods to solve this.  Firstly it helps to understand the concept of modulus – for example 21 mod 6 means the remainder when 21 is divided by 6.  In this case the remainder is 3, so we can write 21 ≡ 3 (mod 6).  The ≡ sign means “equivalent to” and is often used in modulus questions.

Method 1:

1) We try to solve the first part of the question, What number has a remainder of 2 when divided by 3,

to do this we list the values of x ≡ 2 (mod 3).  x = 2,5,8,11,14,17……

2) We then look at the values in this list and see which ones also satisfy the second part of the question, What number has a remainder of 3 when divided by 5

From the list x = 2,5,8,11,14,17…… we can see that x = 8 has a remainder of 3 when divided by 5 (i.e 8  ≡ 3 (mod 5) )

3) We now start from 8 and count up in multiples of 15 (3 x 5 because we have mod 3 and mod 5 )

8, 23, 38, 53 …..

4) We look for a number on this list which satisfies the last part of the question, What number has a remainder of 2 when divided by 7?

With x = 8, 23, 38, 53 ….. we can see that x = 23 has a remainder of 2 when divided by 7 (i.e 23 ≡ 2 (mod 7) )

Therefore 23 satisfies all parts of the question.  When you divide it by 3 you get a remainder of 2, when you divide it by 5 you get a remainder of 3, and when you divide it by 7 you get a remainder of 2.  So, 23 is our answer.

The second method is quite a bit more complicated – but is a better method when dealing with large numbers.

Method 2

1) We rewrite the problem in terms of modulus.

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

We assign a = 2, b = 3, c = 2.

2) We give the values m₁ = 3 (because the first line is mod 3), m₂ = 5 (because the second line is mod 5), m₃ = 2 (because the third line is mod 7).

3) We calculate M = m₁m₂m₃ = 3x5x7 = 105

4) We calculate M₁ = M/m₁ = 105/3 = 35
M₂ = M/m₂ = 105/5 = 21
M₃ = M/m₃ = 105/7 = 15

4) We then note that M₁ ≡ 2 (mod 3), M₂ ≡ 1 (mod 5), M₃ ≡ 1 (mod 7)

5) We then look for the multiplicative inverse of M₁. This is the number which when multiplied by M₁ will give an answer of 1 (mod 3). This number is 2 because 2×2 = 4 ≡ 1 (mod 3). We assign A = 2

We then look for the multiplicative inverse of M₂. This is the number which when multiplied by M₂ will give an answer of 1 (mod 5). This number is 1 because 1×1 = 1 ≡ 1 (mod 3). We assign B = 1.

We then look for the multiplicative inverse of M₃. This is the number which when multiplied by M₃ will give an answer of 1 (mod 7). This number is 1 because 1×1 = 1 ≡ 1 (mod 7). We assign C = 1.

6) We now put all this together:

x = aM₁A + bM₂B + cM₃C (mod M)

x = 2x35x2 + 3x21x1 + 2x15x1 = 233 ≡ 23 (mod 105)

That last method may seem a lot slower – but when working with large numbers is actually a lot quicker.  So there we go – that’s the method that Sun Zi noted more than 1500 years ago.  This topic whilst seemingly quite abstract is a good introduction to number theory – the branch of mathematics which deals with the properties of whole numbers.