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_{1} = 3 (because the first line is mod 3), m_{2} = 5 (because the second line is mod 5), m_{3} = 2 (because the third line is mod 7).

3) We calculate M = m_{1}m_{2}m_{3} = 3x5x7 = 105

4) We calculate M_{1} = M/m_{1} = 105/3 = 35

M_{2} = M/m_{2} = 105/5 = 21

M_{3} = M/m_{3} = 105/7 = 15

4) We then note that M_{1} ≡ 2 (mod 3), M_{2} ≡ 1 (mod 5), M_{3} ≡ 1 (mod 7)

5) We then look for the multiplicative inverse of M_{1}. This is the number which when multiplied by M_{1} 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_{2}. This is the number which when multiplied by M_{2} 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_{3}. This is the number which when multiplied by M_{3} 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_{1}A + bM_{2}B + cM_{3}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.

## 2 comments

Comments feed for this article

February 16, 2014 at 9:09 am

bchen75Fun fact: CRT is a good way to precisely count large numbers of objects (originally in China, soldiers). For instance, tell your soldiers to get into groups of 107, then count the remainders, then get into groups of 17, and count the remainders; now, you have your answer mod 17×107, and if you need to, just use more primes until you get the desired precision.

The Chinese Remainder Theorem is not only a reasonable topic for an introduction to elementary number theory, but also a powerful technique in more advanced mathematics; in fact, it’s general form is true for all commutative rings (if I and J are ideals of R where I + J = R, then R/I × R/J ≅ R/(I∩J) ).

Darn all this is kinda tempting me to change my IA topic now…

June 15, 2014 at 6:13 pm

narindersander1Reblogged this on narindersander1 and commented:

Will be using this with my 8s