Table of Contents

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?

The explanation

We have to search for a number that is divisible by seven but always leaves a remainder of one when divided by $2, 3, 4, 5$, or $6$. 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 $2$ to $6$ with a reminder of $1$. Whether it is divisible by $7$, 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 $6! =720$ which by definition is divisible by the integers $2$ to $6$, and add one to it. Now you have constructed an integer which leaves a remainder of $1$ when divided by $2,3,4,5,$ or $6$ and therefore satisfies the first of the puzzle's conditions. Coincidentally, $(721)$ is also divisible by $7$, 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 $2,3,4,5,6$ and add $1$ to it. Then check whether the result is divisible by 7. If not, find the next smallest common multiple of $2,3,4,5,6$ add 1 to it, then divide by seven and so on. The first number divisible by $7$ is the solution to the puzzle, and it's $301$!

Here be Mathematics

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

$$ \text{lcm}(2,3,4,5,6) = 2 \cdot 3 \cdot 2 \cdot 5 = 60 $$

Using a congruence relation, we can write a general form for the solution: The solution - let's call it $x$ - has the form $x = 60n +1$ for the smallest integer $n$ satisfying:

$$ 60n + 1 \equiv 0 \quad (\text{mod} 7) $$

The first multiple of $7$ that can be written in this form is $301$ which we get for $n=5$.

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 $n$ a bit easier.

Consider the following equivalent statements:

The first n which makes $( 4n +1$) divisible by 7 solves the puzzle, which is of course $5$.

The Chinese Remainder Theorem

Theorem

Given a system of $k$ congruence relations with pairwise coprime moduli $m_1,\cdots, m_k$ then there exists a unique solution up to $ \text{mod } M$, where $M= m_1m_2\cdots m_k$.

Furthermore, if $0 \le a_i \lt m_i: \forall i$, then there exists one and only one $0 \le x \lt M$ and $a_i$ is the remainder of the Euclidean division of $x$ by $m_i$

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 $M_i = \frac{M}{m_i} = m_1 \cdot m_2 \cdots m_{i-1} \cdot m_{i+1} \cdots m_k$. Since all the moduli $(m_i$) are coprime, then it is easy to see that the greatest common divisor of $(M_i$) and $(m_i$) is $(1$). Write:

$$ \text{gcd}(M_i,m_i) = 1 $$

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

$$ x_iM_i \equiv 1 \quad (\text{mod } m_i) $$

For any other index $j \neq i$, $m_j$ will divide $M_i$ by definition. In other words:

$$ x_iM_i \equiv 0 \quad (\text{mod } m_j)\quad \forall j\neq i $$

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

$$ x = \sum_{i=1}^{k} x_i M_i a_i $$

and check for any $i$:

Since we already know that $x_iM_i \equiv 1 \quad (\text{mod } m_i)$, the equivalence above simplifies to:

$$ x \equiv a_i \quad (\text{mod } m_i) $$

which proves the statement of the theorem.

remarks

In the proof above we have constructed a solution $x$ for a system of congruences. However, our solution still relies on an existence theorem for all the $x_i$. 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:

$$ x_iM_i \equiv 1 \quad (\text{mod } m_i) $$

$x_iM_i$ divided by $m_i$ will have a remainder of 1. Meaning that $x_iM_i \pm 1 $ is a multiple of $m_i$.

Write:

Without loss of generality we can write this as:

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,$60$, since it encodes the first five congruences:

$60$ and $7$ are coprime, and the divisors $1$ and $0$ are less than $60$ and $7$ respectively. Applying the theorem, the solution becomes:

$$ x \equiv x_1 M_1 a_1 + x_2 M_2 a_2 \quad (\text{mod } 7\cdot60) $$

where

$$ \Rightarrow x \equiv 7x_1 + 0 \quad (\text{mod } 420) $$

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

$$ 1 = 7x_1 + s60 $$

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

$$ 1 = 7(-17) + (2)60 $$

$$ \Rightarrow x \equiv -119 \quad (\text{mod } 420) $$

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

$$ \Rightarrow \boxed{x = -119 + 420 = 301} $$