Chinese Remainder Theorem

I want to discuss the 'ideai behind the famous Chinese Remainder Theorem. Let us leave the jargon and start our exploration by a problem.


Find a number that leaves remainder 1, when divided by 5, 7 and 13.

Clearly such a number can be found by trial. A stupid method is to check out all the numbers (at least some them) which leaves 1 as remainder when divided by 5 (we choose 5 because it is the smallest).

6, 11, 16, 21, 26, 31, 36, 41,...

The above sequence of numbers leave 1 as a remainder when divided by 5. Now the second condition is that, our required number must generate 1 as a remainder when divided by 7. Clearly that number is one of the numbers of the above sequence. We check out the remainders when divided by 7.

Number	Remainder when divided by 7
6	6
11	4
16	2
21	0
26	5
31	3
36	1 (WHOA!)

So 36 is the first number that fulfills the second condition. It leaves remainder 1 when divided by 5 as well as 13. Note that 36 is the first number with such a character. 71, 106 etc. are other numbers with such characteristic.

Anyways, we move to the third condition now. The number must leave a remainder 1 when divided by 13. A little introspection will bring the idea of product + 1 to the forefront. Note that 36 = 5*7 + 1; 70=5*7(*2)+1; 106 = 5*7(*3)+1; i.e. each of the numbers which leaves remainder 1 when divided by 5 and 7, contains 5 and 7 (as prime factors) and 1 more (rightly so!).

Therefore our required number is 13*5*7*(any number from 1 toward infinity) +1. In short we write 455k + 1 where k is any natural number.

Now we move forward with the second problem.


Find all integers that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11. 

A brain-breaker idea will be to check out all the numbers that produce a remainder 3 when divided by 5. The following is the least of such numbers.

3, 8, 13, 18, 23, 28, 33, 38,

Then we shoot the numbers of the above sequence by 7 and find that 33 is a number that produces remainder 5 when divided by 7 (33=4*7 + 5). Can we guess a second number that produces remainder 5 when divided by 7? Clearly 68 is a second number with the same feature. Lets try 1 more (and while we do this lets us ask our brain the method it is using to compute the number). 103! Yes, we add 35 to the preceeding number (we still need to REASON why this works). But before that let us assure ourselves that 103 = 5*20 + 3 and 103 = 7*14 + 5. Also we need to be convinced that when we jumped 35 we did not miss any number with 3 and 5 as remainders when divided by 5 and 7 respectively.

Number	Remainder when divided by 7
3	3
8	1
13	6
18	4
23	2
28	0
33	5
38	3
43	1
48	6
53	4
58	2
63	0
68	5
73	3
78	1
83	6
88	4
93	2
98	0
103	5

So we did not miss any one number.Hmm, that is good.And one more observation. The remainders are repeating (3164205 3164205 ... so on). We will learn later that is a beautiful (and logical) consequence of the concept of divison.

So far so good. Our brain tells us: Find the first number with the character (remainder 3, 5, 7 when divided by 5, 7, 11) and add 5*7*11 to that to find all such numbers. The challenge is however to find that FIRST NUMBER.