Cracking the Code: A Deep Dive into the Chinese Remainder Theorem

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

Find a number that leaves the 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 of them) which leaves 1 as the 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 leaves 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 remainder when divided by 7.

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 characteristics.

Anyway, we move to the third condition now. The number must leave a remainder of 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 of 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 the remainder 5 when divided by 7 (33=4*7 + 5). Can we guess a second number that produces the remainder of 5 when divided by 7? Clearly, 68 is a second number with the same feature. Let's try 1 more (and while we do this let us ask our brain the method it is using to compute the number). 103! Yes, we add 35 to the preceding 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.

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

So far so good. Our brain tells us to 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.