|
The problem known as the chinese puzzle
first appears in the fourth century document written
by master Sun.
Mathematically speaking the chinese puzzle problem is to find a number defined by its remainders for a given set of dividers. |
| The Chinese remainder theorem guarantees that there is exactly one integer that has the given remainders. This is true when the divisors are relative primes, and the integer is greater or equal zero and smaller than the product of the divisors. |
|
Example I (for divisors 3 and 5) The numbers 3, 5 are primes (only divisors are 1 and the number iself). Any interger 1-15 is represented uniquely by the remainders with respect to the divisors, 4 and 5. |
|
ch(3,5:1,3) corresponds to 13 because 13%3=1, 13%5=3. ch(3,5:2,4) corresponds to 14 because 14%3=2, 14%5=4. ch(3,5:1,0) corresponds to 10 because 10%3=1, 10%5=0. |
|
Example II (for divisors 3, 4 and 5) The numbers 3, 4, and 5 are relative primes (greatest common denominator 1). Any interger 0-59 is represented uniquely by the remainders with respect to the divisors, 4,3 and 5. |
|
ch(3,4,5:1,1,3) corresponds to 13 because 13%3=1, 13%4=1, 13%5=3. ch(3,4,5:2,2,4) corresponds to 14 because 14%3=2, 14%4=2, 14%5=4. ch(3,4,5:1,3,4) corresponds to 19 because 19%3=1, 19%4=3, 19%5=4. |