Problem Description

What is the smallest number that can be divided by 6, leaving a remainder of 5; by 5  leaving 4; and by 4 leaving 3?

Source: The Mensa (c) Puzzle Calendar for Oct 18. 2001;

Background & Techniques

Here's an introduction to Chinese Remainder problems.    They're called "Chinese Remainder" because the problem and the theorem which defines when they can be solved were both known to the early Chinese scholars.   The earliest known example of this type of problem was published in the 3rd, 4th or 5th  century AD by Chinese scholar,  Sun Zi, in a book titled  "Master Sun's Mathematical Manual".

Here's Sun Zi's original problem: 

We have a number of things, but we do not know exactly how many. If we count them by threes we have two left over. If we count them by fives we have three left over. If we count them by sevens we have two left over. How many things are there?"

His solution  is the following poem:

Three septuagenarians walking together, 'tis rare!

Five plum trees with twenty one branches in flower,

Seven disciples gathering right by the half-moon,

One hundred and five taken away, lo the result shall appear!

I'm glad we have computers!  

The Chinese Remainder Theorem is not particularly easy to understand -  it just says that under certain conditions (i.e. the divisors have no common factors), there is a solution:

If m₁, ..., m_k are pair-wise relatively prime moduli and a₁, ..., a_k are natural numbers, then there exists a natural number x that simultaneously satisfies x = a_i mod(m_i), i=1, ..., k.

Here mod is the modulus  (or remainder) operation, a mod (b) is the remainder when a is divided by b.  

In terms of the original problem: "Find N such that N mod(6)=5, N mod(5)=4, and  N mod(4)=3".    Notice that two of our factors (6 and 4) are not relatively prime so the Chinese Remainder Theorem doesn't say whether it can be solved or not.   Not very helpful.  (In fact, it is solvable, but it's easy to change the required remainder values to find cases that are not solvable.)

Analytical solutions for this type of problem are hard, at least for me.  But a computer and Delphi make solving a pretty easy.  We'll just take in the three divisors and the three remainders and try numbers from 1 to 1,000 looking for one that meets the requirements.  

Two versions of the program are included.  

•  Chinese Remainders 1 is bare bones and solves the original problem stated  above.  It has about 50 lines of user written code, so we'll call it  Beginner's level.  
•  Chinese Remainders 2 adds some error checking and the ability to solve more problems. (And it checks numbers up to 10,000,000 before giving up.)  A couple of additional samples are included and the grid can be resized to handle larger or smaller user entered problems.  200 or so lines of code make this version Intermediate level.  

Addendum August 6, 2003:  Today's Mensa Puzzle Calendar posed another Chinese Remainder problem involving stamp in a stamp album.  I added it to the sample problems in Chinese Remainder 2, and also fixed the program so that extra blank lines in the input grid are ignored rather than reporting an error.    If you check the source code, the Tmemos that contain the problem descriptions are all defined in the same location which can make it a little difficult to change, or even find them when workin in Delphi's editor.  A tip is to right click on the top memo and then click "Send to back" to view the next one in line (called Z-order by Windows programmer types).

Running/Exploring the Program 

• Browse source extract (Version 1)
• Download source (Versions 1 and 2)
• Download  executable (Version 2)

Suggestions for Further Explorations

Is there a test to determine  that a particular problem has no solution?