The Puzzle

A woman goes to the market with a basket full of eggs. On her way, a horse bumps into her, causing her to drop the basket and break all the eggs. The horse's owner feels guilty and asks how many eggs she had so he can compensate her. She replies:

"I don't remember the exact number of eggs, but I do remember this:

• When I tried to group the eggs two at a time, there was one egg left over.
• The same happened when I grouped them three at a time, four at a time, five at a time, and six at a time—there was always one egg left over.
• However, when I grouped them seven at a time, there were no eggs left over."

What is the smallest number of eggs she could have had?

Explanation

We have to search for a number that is divisible by seven but always leaves a remainder of one when divided by , or . So your first question should be: why should such a number exist? Can I define arbitrary conditions of remainders, as above in the puzzle and find solutions for them, or is this puzzle unique in some way?

It is fairly easy to find a number not divisible by any of the integers to with a reminder of . Whether it is divisible by , is a different story. An answer to this question is provided by the "Chinese remainder theorem" and I will discuss it a bit further down below.

Keep in mind that solving the puzzle is straightforward, but I’m more interested in a formal approach. Specifically, I’m looking for a method to determine whether a general solution exists, along with a formula or algorithmic approach to compute it.

Naturally, I realize that the abstract mathematical questions I posed above are not the first questions which come to mind when one encounters this puzzle, so I will start by presenting the direct easy solution first.

A naive approach

Consider which by definition is divisible by the integers to , and add one to it. Now you have constructed an integer which leaves a remainder of when divided by or and therefore satisfies the first of the puzzle's conditions. Coincidentally, is also divisible by , but it does not solve the puzzle, because it is not the smallest possible solution.

An educated approach

The idea is simple: compute the least common multiple of the integers and add to it. Then check whether the result is divisible by 7. If not, find the next smallest common multiple of add 1 to it, then divide by seven and so on. The first number divisible by is the solution to the puzzle, and it's !

The Mathematics

Let's start by writing the idea above formally. The least common multiple of these integers is:

Using a congruence relation, we can write a general form for the solution: The solution - let's call it - has the form for the smallest integer satisfying:

The first multiple of that can be written in this form is which we get for .

A trick using congruence relations

There is a simple trick that makes use of congruence relations. This trick makes the arithmetic - and therefore the process of trial and error - for finding a bit easier.

Consider the following equivalent statements:

The first n which makes ) divisible by 7 solves the puzzle, which is of course .

Note These statements are equivalent because congruence relations are compatible with algebraic structures. In this case the algebraic structure is the integer ring , with the conventional addition and multiplication.

The Chinese Remainder Theorem

Theorem

Given a system of congruence relations with pairwise coprime moduli then there exists a unique solution up to , where .

Furthermore, if , then there exists one and only one and is the remainder of the Euclidean division of by

This is one of multiple possible statements of the theorem. It is of course a modern formulation but the theorem originates from 5th century china, in a book on mathematics. It appeared as conjecture without proof or algorithm.

Great… how does this help us in actually finding the solution? Well, the theorem has a proof by construction. This means that we can prove the theorem by constructing a solution for a general form of the puzzle above.

Proof of existence by construction

Let . Since all the moduli ) are coprime, then it is easy to see that the greatest common divisor of ) and ) is ). Write:

A well known result in number theory says that if two integers are coprime - as is the case with ), then there exists an integer¹ - call it - such that:

For any other index , will divide by definition. In other words:

This is all we need to construct an integer which solves the system of congruence relations and proves the theorem. Consider:

and check for any :

Since we already know that , the equivalence above simplifies to:

which proves the statement of the theorem.

remarks

In the proof above we have constructed a solution for a system of congruences. However, our solution still relies on an existence theorem for all the . Unless we find a systematic way to compute these integers, we would not be able to find a solution to the puzzle easily.

With that in mind, consider again the statement:

divided by will have a remainder of 1. Meaning that is a multiple of .

Write:

Without loss of generality we can write this as:

Note Note that 1 is the greatest common divisor of and and the equation above is called Bézout's identity.

The factors are called Bézout's coefficients, and they are computed using the extended Euclidean algorithm of division at the step before last.

Bézout's identity and the Euclidean algorithm warrant an article by themselves and are therefore beyond the scope of this post.")}}

Application of the theorem

First we need to formulate the puzzle in a way that is compatible with the theorem. We could write:

We can improve on this by using the least common multiple of these integers,, since it encodes the first five congruences:

and are coprime, and the divisors and are less than and respectively. Applying the theorem, the solution becomes:

where

Now it only remains to compute Bézout's coefficients for the identity:

As mentioned before, those coefficients are computed from the Euclidean algorithm of division. In this case we have:

The solution is unique up to modulo , meaning that there are multiple solutions, which are apart. We know from the theorem that there is one and only one solution between and :