Home  |  Academic |  Personal  |  Research  |  Site Map  |  Search Web  |  Email  |  Links

Back to Class Notes (M326)

Chinese Remainder Theorem:

Ask someone to pick a number from 1 to 1000.  they must tell you the remainder that they get when they divide their number by first 7, then 11, then 13.  You then have enough information to tell what their original number was.  Here is how to do it.

Let's say the remainders after dividing by 7, 11, and 13 respectively were a, b, and c.  Compute the expression:

     715a + 364b + 924c

This number has the desired properties but it is generally larger than 1000.  To determine your friend's number, keep subracting 1001 from this result until you get a number less than 1000.

Example:

Let's say your friend's number were 200.

Then a=4, b=2, and c=5

Therefore:   715(4) + 364(2) + 924(5) = 8208
If you subtract 8 groups of 1001, then you get,

    8208 - 8008 = 200

Your problem is to figure out how this trick works.  The answer lies in the following tables of modular arithmetic mod 7, mod 11, and mod 13.