All 1 entries tagged Cross-Cultural-Mathematics

Teaching Chinese Remainder Theorem

Introduction

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

• How the table was generated? Answer
  • Working out the rules that build the table will prove the Chinese remainder theorem;
  • For each n from 0 to 4x5-1, row = remainder of n/4, column = remainder of n/5;
• What other properties do the table exhibit? Answer
  • Each number from 0 to 19 appears exactly once!
  • The table shows a simple form of the Chinese remainder theorem: there exists an unique (modulo) solution to the problem of finding the number from its remainders provided the divisors are mutual primes.
  • Notice that the numbers 0 to 19 are arranged in a 4x5 table. In a slightly advanced form, the Chinese remainder theorem states that the clockwork arithmetic of n (ring of modulo n) is identical (isomorphic) to the combined of the clockwork arithmetic of p and q (product of the rings of modulo p and q) if p and q are mutual primes.
  • The Chinese remainder theorem holds for a finite set mutual primes.
  • The following questions further the exploration.

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
   • The answer to question 1 is 12. It can be verified easily.
   • Alternatively, we notice that 17 corresponds to the remainders of 1 and 2 when divided by 4 and 5 respectively. Whereas 15 corresponds to the remainders of 3 and 0 when divided by 4 and 5 respectively. Then, adding the corresponding remainders 1+3 and 2+0 yield 0 and 2. Looking up the table, 12 is the number corresponding to the remainders of 0 and 2 when divided by 4 and 5 respectively!
   • Similar technique can be applied to find the answer of the multiply in question 2.
4. What is the remainder of (17 x 17) when divided by 20? Answer
   14
5. Find the number(s) k such that (k x k) when divided by 20 is 9? Answer
   There are four answers: 3, 7, 13 and 17. This great surprise has an important application in cryptography. There are multiple solutions to the root of a number. Whereas computing the power (exponentiation) of a number is easy, obtaining an unique root of a number is not possible. This class of functions is known as the one-way function or the trap door function. The trap door functions are useful because they make guessing the decryption difficult!

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.

: 31 Mar 2011 22:57 |  Tags: Cross-Cultural-Mathematics |  Comments (0) |  Close comments |  Report a problem