How Many Eggs Were in the Basket?

Trying every number up to 400 is slow. Start with only some of the rules and look for a pattern.

Only twos and threes. Which numbers leave 1 egg over when taken out in twos, and also 1 over in threes? Try 1, 2, 3, … with the widget, or in your head. You find 1, 7, 13, 19, 25, …: they go up in steps of 6.

• a.Why steps of 6? Before reading on, try to say why.
• b.Now add the fours. Which numbers leave 1 over in twos, threes and fours? What is the step now?
• c.And with twos, threes, fours, fives and sixes, all leaving 1?

That is the trick for the first five rules: they all say the same thing, take one egg away and the rest is a multiple of 60. That is the lowest common multiple at work.

Now only the sevens are left. Go along 1, 61, 121, 181, … and divide each by 7:

Eggs	1	61	121	181	241	301
Left over in sevens	1	5	2	6	3	0

301 eggs: 301 = 43 × 7, and 300 is a multiple of 60, so 301 leaves 1 over in twos, threes, fours, fives and sixes.

And why does the next answer come 420 eggs later? It must be a multiple of 60 more than 301 and a multiple of 7 more, so a multiple of their LCM, 420: 301, 721, 1,141, …. Her “fewer than 400” picks out one.

The eggs were kind: five of the six rules said the same thing. In the oldest puzzle of this kind we know of, every remainder is different. It comes from a Chinese book written some time between the 3rd and 5th centuries (no one knows exactly when), the Sunzi suanjing (“Master Sun’s Mathematical Manual”, chapter 3, problem 26). In our own words:

There are some things, we don’t know how many. Counted in threes, 2 are left over. Counted in fives, 3 are left over. Counted in sevens, 2 are left over. How many things are there?

The quickest way by hand is to go up in the biggest steps. The numbers that leave 2 over in sevens are 2, 9, 16, 23, 30, …. Check each against the fives (3 left over) and the threes (2 left over): 2 leaves 2 in fives, 9 leaves 4, 16 leaves 1, and 23 leaves 3. And 23 = 7 × 3 + 2 leaves 2 in threes. So 23, and the next answers are 23 + 105, 23 + 210, …, since 3 × 5 × 7 = 105.

That is searching. Sunzi gives a recipe that turns any three remainders straight into the answer. Here it is as a trick: a friend thinks of a number from 0 to 104 and tells you only its remainders on dividing by 3, 5 and 7, and you name it.

But first a deeper question. Why should every choice of remainders belong to exactly one number from 0 to 104? There are 3 × 5 × 7 = 105 choices and 105 numbers; if two numbers shared their remainders, some choice would be left with none. The next section shows that never happens.

Take just two divisors, 3 and 5. Write each number in a table: the row is what it leaves on dividing by 3, the column what it leaves on dividing by 5. The number 7 leaves 1 in threes and 2 in fives, so it goes in row 1, column 2.

Try these with the widget.

• a.With 3 and 5, how does each number move from the one before? What happens at the edges?
• b.Does any square of the 3 × 5 table get two numbers from 0 to 14? Does any stay empty?
• c.Now 4 and 6. What is different?

Here is why 3 and 5 can’t share a square between two numbers from 0 to 14. Suppose two of them, say m and n, landed on the same square. Then they leave the same remainder on dividing by 3, so their difference n − m is a multiple of 3; and they leave the same remainder on dividing by 5, so n − m is a multiple of 5 too. A multiple of both 3 and 5 is a multiple of their LCM, 15. But two different numbers from 0 to 14 differ by at least 1 and at most 14: no multiple of 15 fits. So no two numbers from 0 to 14 share a square.

Now count. 15 numbers, 15 squares, and no square gets two: then no square is left empty either, like 15 people in 15 chairs with no one sharing. So every pair of remainders happens, exactly once, from 0 to 14.

The same argument works for any divisors that share no common factor. Two numbers that leave the same remainders differ by a multiple of every divisor, so by a multiple of their LCM; and when no two of the divisors share a factor, the LCM is their product, N. So no two numbers from 0 to N − 1 leave the same remainders; and since there are N numbers and N choices of remainders, the counting goes as before: every choice is taken, exactly once. That is the theorem.

It is called the Chinese remainder theorem, after Sunzi’s problem (sometimes Sunzi’s theorem). In the language of clock arithmetic: if $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$ and $x \equiv 2 \pmod 7$, then $x \equiv 23 \pmod{105}$.

What it means: a number from 0 to 104 and its three remainders are two ways of writing the same thing. Computers use exactly that (below): work with small remainders, and rebuild the big number only at the end.

The counting proof says the answer exists, but not how to find it without searching. Sunzi’s recipe does: multiply the leftover in threes by 70, the leftover in fives by 21, the leftover in sevens by 15, add, and take away 105 as often as you can. For his puzzle: 2 × 70 + 3 × 21 + 2 × 15 = 233, and 233 − 2 × 105 = 23.

The secret is in what 70, 21 and 15 leave:

Number	Left over in threes	in fives	in sevens
70	1	0	0
21	0	1	0
15	0	0	1

Each is a building block that leaves 1 for one divisor and 0 for the others. 70 is a multiple of 5 and 7 that leaves 1 in threes; 21 is a multiple of 3 and 7 that leaves 1 in fives; 15 is a multiple of 3 and 5 that leaves 1 in sevens. So 2 × 70 leaves 2 in threes and 0 in fives and sevens; 3 × 21 leaves 3 in fives and 0 in the others; 2 × 15 leaves 2 in sevens. Add them, and each divisor sees only its own block: 233 leaves 2, 3 and 2. Taking away 105s changes no remainder, since 105 is a multiple of all three. It only brings the number down to between 0 and 104.

How do you find a block? For the threes, try multiples of 5 × 7 = 35: 35 leaves 2, 70 leaves 1. For the fives, 3 × 7 = 21 already leaves 1; for the sevens, 3 × 5 = 15. With big divisors, trying is slow; the block solves a linear Diophantine equation, 35k = 3y + 1, which Euclid’s algorithm run backwards solves at once (the kuttaka of topic 6, linked at the end).

The theorem needs divisors with no common factor. What goes wrong without it? Try this: a number leaves 1 over in fours and 2 over in sixes. Search as long as you like; there is none. A number that leaves 1 in fours is odd (4 is even, so one more than a multiple of 4 is odd). A number that leaves 2 in sixes is even. No number is both. The rules contradict each other, though each is fine alone.

Change the second rule to “3 over in sixes”, and now both say the number is odd. Then there are answers: 9, 21, 33, …, every 12, the LCM of 4 and 6, not every 24. That is the table for 4 and 6 in the widget: the squares reached are exactly those where the two remainders are both odd or both even. Why are all of those reached? Two numbers on the same square differ by a multiple of 4 and of 6, so of 12; so 0 to 11 land on 12 different squares. And there are exactly 12 squares whose remainders match like that (2 even rows × 3 even columns, and 2 odd rows × 3 odd columns). The walk fills every one of them.

The egg puzzle passed this test: its divisors 2, 3, 4, 5, 6 share plenty of factors, but every rule said “1 over”, so they agreed, and together said only “1 over in 60s”.

Always one short. A basket leaves 1 over in twos, 2 over in threes, 3 in fours, 4 in fives, 5 in sixes, and comes out even in sevens. Every remainder is one less than the divisor: add one egg and every count would come out even. So the number is one less than a multiple of 60: 59, 119, 179, …. The first that comes out even in sevens is 119 = 17 × 7.

Bhaskara II set almost the same puzzle in his Bijaganita (12th century), in its chapter on equations with several unknowns, solved with the kuttaka. In Colebrooke’s 1817 English translation: “What number is it, which, being divided by six, has five for a remainder; or divided by five, has a residue of four; or divided by four, has a remainder of three; or divided by three, leaves two?” Bhaskara’s working gives 59; his commentator Krishna adds that with the next choice it is 119.

Ibn al-Haytham’s answer. About a thousand years ago, Ibn al-Haytham (about 965–1040, Basra and Cairo, better known for his work on light) asked for exactly the egg-seller’s number: leaving 1 on dividing by 2, 3, 4, 5 and 6, and nothing on dividing by 7. He gave a surprising method: multiply the divisors 1 × 2 × 3 × 4 × 5 × 6 and add one. That is 721, which is 7 × 103. It isn’t the smallest answer (301 is), but it works, and not by luck: a theorem now named after John Wilson says that for any prime p, 1 × 2 × ⋯ × (p − 1) + 1 divides exactly by p. Try it with 5: 1 × 2 × 3 × 4 + 1 = 25.

• Computing with very big numbers: exact calculations with large whole numbers are often done with remainders on dividing by several small numbers, each small enough for the computer’s own arithmetic, and the answer put together at the end (multi-modular computation).

• How Can Two Strangers Agree on a Secret in Public? Remainders, powers, and the locks on every website, where this topic’s theorem does the heavy lifting.
• Can You Buy 100 Birds with 100 Coins? Linear Diophantine equations and the kuttaka, the way to find Sunzi’s building blocks for big divisors.
• How Do You Find Every Right Triangle with Whole Sides? Another whole-number puzzle, where remainders on dividing by 4 decide which sides are odd.
• What Day of the Week Will Your 100th Birthday Be? (Grades 6–8) Clock arithmetic and the sign ≡, on the week’s seven-day clock.
• Which Amounts Can You Never Pay with 3s and 5s? (Grades 6–8) Numbers in rows by their remainders, another table of the same kind.
• Computing, Going Further: Why Can’t a Formula Convert Bikram Sambat to AD? Calendars as data, where cycles that never line up neatly make the problem hard. (Coming soon.)