nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Chinese Remainder Theorem and the Chinese Problem

Number Theory Contents

Page Contents

  1. Chinese Problem
  2. Chinese Remainder Theorem
  3. Solving the Problem Using Successive Substitution
  4. Rationale


Chinese Problem

The Chinese Problem was first introduced by Sun Tsu (460 AD), and problems of that kind are often referrred to as the Chinese Problem:Oystein Ore mentions the following problem due to Brahmagupta (598)
When the eggs are taken out of a basket 2, 3, 4, 5, 6, 7 at a time, the remainders 1, 2, 3, 4, 5 and 0. How many eggs were in the basket?

Apparently such problems amused both the high and the low at that time. The divisors are not relatively prime, and relative primality is not a condition for solvability.

Chinese Remainder Theorem

The Chinese Remainder Theorem is a statement of the conditions under which a set of simultaneous congrent equations is solvable. We will answer this question later.

Solving the Problem Using Successive Substitution

We have already used a method to solve think kind of problem. The following "low-tech" method is more efficient, however.

When the eggs were taken out 2 at a time, the remainder was 1. We can write an equation:
2k+1       [1.1]
to represent the solutions.

When this equation is divided by 3, the remainder is 2, so
(2k+1)/3 gives a remainder 2
By probing we find this value is k=2, and
2k+1=5
5 is a solution so far to division by 2 and 3. If we write a new equation:
5+2·3·k=5+6·k,     [1.2]
This equation results in 1 when divided by 2 and 2 when divided by 3, for all integers k. We now require that:
(5+6·k)/4     [1.3]
gives a remainder 3, simplifying 1.3:
1+k+(1+2k)/4   [1.4]
Clearly, k=1, so (from 1.2)

5+6·k=11
So far we have a number 11, which divided by 2, gives 1, by 3, gives 2 and by 4, gives 3 as required.

We can preserve these results by writing the new equation:
11+3·4·k=11+12·k,    [1.5]
because 3·4=12 is divisible by 2, 3, and 4, so our number will give the required results for division by 2, 3 and 4 for all integers k.

We now require that division by 5 gives a remainder 4, or
(11+12·k)/5 gives a remainder 4

(11+12·k)/5=
2+2·k+(1+2·k)/5 gives a remainder 4
So, by testing k=4, and (from 1.5)

11+12·4=59
Writing our next equation:
59+3·4·5·k=59+60·k  [1.6]
because 3·4·5=60 is divisible by 2, 3, 4, and 5

We require that this gives a remainder 5 when divided by 6:

(59+60·k )/6  gives a remainder 5, which it actually does, for all integers k

Our final equation, which comes out even when divided by 7 is:
59+3·4·5·k      [1.7]
because 3·4·5=60 is divisible by 2, 3, 4, 5 and 6

We require that:
(59+60·k)/7 comes out even.

8+8·k+(3+4·k)/7 [1.8]
When k=1, then 1.8 comes out even.

Our new number is therefore:
59+60=119
Therefore the minimum number of eggs in the basket is 119.


Rationale

We normally think of natural numbers here.
Let a1 be a natural number such that, when divided by m1, gives a remainder r1, where 0≤r1<m1 (that is, m1 is the least positive remainder when a1 is divided by m1). Then we can write:
a1+k·m1       [2.1]

This will always give a remainder r1 when divided by m1, whatever the value of integer k. We can show this is true by dividing Equation 2.1 by m1, and noting this results in an integer, k, and a remainder a1/m1, which is r1.

Suppose that a2 is a natural number which when divided by m1, gives a remainder r1 and when divided by m2, gives a remainder r2. Then:
a2+k·m1·m2       [2.2]  
Will always give a remainder r1, when divided by m1, and a remainder a2, when divided by m2.

In general, if an is a number that when divided by m1 gives r1, by m2, gives r2... by mn, gives rn. Then:
an+k·m1·m2·...mn [2.3]
always gives the correct remainder when divided by the respective m's, as can be verified by direct division.

In effect, 2.3 is the solution to the set of
setOfEquations.gif [2.4]












Number Theory Contents

Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults