All entries for Thursday 31 March 2011

March 31, 2011

Teaching Chinese Remainder Theorem


This teaching idea was a spin-off of the subject session on "Cross-cultural mathematics". I based my material largely on the lecture notes on a course of Cryptography by Leonid Reyzin of the Computer Science Department at Boston University. The Chinese remainder theorem can be stated in different levels of algebraic abstraction. We can introduce the Chinese remainder theorem not only for cultural curiosity, but also for its mathematical contents and practical applications. Proving the Chinese remainder theorem in full generality is normally investigated in the abstract algebra course at university. In the following questions and examples, I try to make the topic accessible to school level students. In fact, solving problems using the Chinese remainder theorem were examination questions for scholars in ancient China! Nowadays, the Chinese remainder theorem type of questions appear in Maths Challenges for schools!

Examples and questions

Select two numbers such that their only common divisor is 1. Technically the numbers are known as mutual primes, coprimes or relative primes. Consider 4 and 5, for example, and investigate the following table

0 1 2 3 4
0 0 16 12 8 4
1 5 1 17 13 9
2 10 6 2 18 14
3 15 11 7 3 19
  • How the table was generated? Answer
  • What other properties do the table exhibit? Answer

Some open questions

  • Choose another pair of mutual primes and show that the rules are still applicable.
  • Choose a pair of non-mutual primes, how do they affect the rules?
  • Choose a pair of mutual primes p and q such that p and q are greater than 100. Find a method to obtain n if the a and b are the remainders when n is divided by p and q.
  • Choose 3 numbers p, q and r such that they are mutually primes. How to solve the problem of finding n if a, b and c are the remainders when n is divided by p, q and r respectively?

Some specific questions

  1. What is the remainder of (17 + 15) when divided by 20?
  2. What is the remainder of (17 x 15) when divided by 20?
  3. How can the table above help to work out the answer of the previous questions? Answer
  4. What is the remainder of (17 x 17) when divided by 20? Answer
  5. Find the number(s) k such that (k x k) when divided by 20 is 9? Answer

An examination question in ancient China

A general counted the number of soldiers in his army. 2, 3 and 2 soldiers stood out of the files if they were ranked in groups of 3, 5 and 7. How many soldiers were there?

On MacTutor at University St Andrews, there is a good reference to the origin of the Chinese remainder theorem.

Application of the Chinese remainder theorem in the RSA algorithm

The RSA algorithm is an encryption and decryption technique used in many privacy applications and electronic commerce.

Search this blog


Most recent comments

  • Hi. I was creating a blogroll and tried to search the internet with blogs that using GeoGebra and fo… by Guillermo Bautista on this entry

Blog archive

Not signed in
Sign in

Powered by BlogBuilder