Chinese Remainders

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 m1, ..., mk are pair-wise relatively prime moduli and a1, ..., ak are natural numbers, then there exists a natural number x that simultaneously satisfies x = ai mod(mi), 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).

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?

Created: Nov 19,2001

Modified: February 18, 2016

 

 

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2016, Gary Darby    All rights reserved.