Problem: An old lady was going to a street market when a reckless kid on a skateboard bumped into her and made her drop a basket full of painted porcelain figurines breaking all of them into many small pieces. The kid's father saw the whole thing and offered to pay for all the damaged items so he asked her how many figurines she had bought. The old lady couldn't remember the exact number, but she remembered that when she had taken them out two at a time, there was one figurine 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 figurines she could have had?

Solution: First, let's formulate this using mathematical notation. Let x = the number of porcelain figurines the old lady originally had. Clearly, x is a positive integer and we also know that:


x % 2 = 1
x % 3 = 1
x % 4 = 1
x % 5 = 1
x % 6 = 1
x % 7 = 0

where % is the modulus operator. These equations can also be written as congruence relationships:


x = 1 (mod 2)
x = 1 (mod 3)
x = 1 (mod 4)
x = 1 (mod 5)
x = 1 (mod 6)
x = 0 (mod 7)

If you haven't already figured it out, this is a problem that derives from the Chinese Remainder Theorem. This theorem deals with solving simultaneous modular arithmetic equations.

The least common multiple of 2,3,4,5,6 is 60, thus the first 5 equations above can be reduced to a single equation:

x = 1 (mod 60)

So clearly the solution to the simultaneous equations is a number that is a multiple of 7 and gives a remainder of 1 when divided by 60. We can therefore examine numbers of the form: 60m+1 where m=0,1,2,3,... Here is the first 10 numbers in this sequence:

1, 61, 121, 181, 241, 301, 361, 421, 481, 541, ...

Starting with the lowest number and dividing each by 7 we can quickly determine that 301 is the answer since it is the first number divisible by 7.

Bookmark and Share