INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

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

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. Let's 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 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.

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

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.

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIAL
Google