[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

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.  

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).

November 4, 2010:  A new C.R. problem from our Mensa Puzzle-A-Day calendar today has been added to the set of sample programs.

Christine has a number of flowers that she wants to put into arrangements.
If she puts them in groups of 2 she has 1 left over.
If she puts them in groups of 3 she has 2 left over.
If she puts them in groups of 4 she has 3 left over.
If she puts them in groups of 5 she has 4 left over.
If she puts them in groups of 6 she has 5 left over.
If she puts them in groups of 7 she has 0 left over.
What is the smallest number of flowers that Christina could have?

This is an easier version of a problem dating from the 7th century: An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Running/Exploring the Program 

Suggestions for Further Explorations

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

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.