Home  |  AcademicPersonal  |  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.

 143 = 11x13 Multiples of 143 Value  Mod 7 91  = 7x13 Multiples of 91 Value  Mod 11 77 = 7x11 Multiples of 77 Value  Mod 13 143 286 429 572 715 858 1001 3 6 2 5 1 4 0 91 182 273 364 455 546 637 728 819 910 1001 3 6 9 1 4 7 10 2 5 8 0 77 154 231 308 385 462 539 616 693 770 847 924 1001 12 11 10 9 8 7 6 5 4 3 2 1 0

Home  |  AcademicPersonal  |  Research  |  Site Map  |  Search Web  |  Email  |  Links