Chinese Problem was first introduced by Sun Tsu (460 AD), and problems
of that kind are often referred to as the Chinese Problem:Oystein Ore mentions the following problem due to Brahmagupta (598)
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?
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
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. ■
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 [2.4]