Chinese Remainder Puzzles

A basket of eggs, counted in groups, always has some left over. Counted by twos, one is left. By threes, two are left. By fives, four are left. What's the smallest number of eggs in the basket?

Try it before reading on — you can brute-force small cases in your head, but the puzzle is really asking for a method, since interviewers love to follow up with bigger, uglier divisors where guessing stops working.

The clues, translated

Each clue is a remainder statement. "Left one over when counted by twos" means the count $N$ satisfies $N \equiv 1 \pmod 2$ — in words, dividing $N$ by 2 leaves remainder 1. Our basket gives three such clues:

$N \equiv 1 \pmod 2, \qquad N \equiv 2 \pmod 3, \qquad N \equiv 4 \pmod 5$

Each one alone allows infinitely many values of $N$: 1, 3, 5, 7, 9, ... satisfy the first; 2, 5, 8, 11, ... satisfy the second. The question is what happens when all three must hold at once.

Why a unique answer exists at all

Here's the fact that makes this whole puzzle type work, known as the Chinese Remainder Theorem. If the divisors — here 2, 3, 5 — share no common factors with each other (they're pairwise coprime), then a system of remainder clues against them has exactly one solution modulo the product of the divisors. The product here is $2 \times 3 \times 5 = 30$, so there is exactly one answer between 0 and 29, and every valid basket size is that answer plus a multiple of 30.

The intuition: think of three clock faces with 2, 3, and 5 hours on them respectively, all ticking together as $N$ counts up 0, 1, 2, 3, .... The three hands return to their starting positions simultaneously only once every $\mathrm{lcm}(2,3,5) = 30$ steps, because 2, 3, and 5 share no common factor. Until then, every combination of hand positions is visited exactly once — so the combination "1 on the first clock, 2 on the second, 4 on the third" pins down $N$ uniquely within that 30-step cycle.

Solving the egg basket

The fastest hand method is successive substitution: solve two clues at a time, fold the result into a single new clue, then bring in the next divisor.

Step 1 — combine the mod-2 and mod-3 clues. Numbers that are $1 \pmod 2$: 1, 3, 5, 7, 9, 11, .... Which of these are also $2 \pmod 3$? Check them in order: $1 \to 1 \pmod 3$ (no), $3 \to 0$ (no), $5 \to 2$ (yes). So $N \equiv 5 \pmod 6$ — the combined clue, since $\mathrm{lcm}(2,3) = 6$.

Step 2 — fold in the mod-5 clue. Numbers that are $5 \pmod 6$: 5, 11, 17, 23, 29, .... Which are also $4 \pmod 5$? Check: $5 \to 0$ (no), $11 \to 1$ (no), $17 \to 2$ (no), $23 \to 3$ (no), $29 \to 4$ (yes). So $N \equiv 29 \pmod{30}$.

Answer: the smallest basket has 29 eggs. Quick sanity check: $29 = 2 \times 14 + 1$ (one left over by twos, correct), $29 = 3 \times 9 + 2$ (two left over by threes, correct), $29 = 5 \times 5 + 4$ (four left over by fives, correct). All three clues hold, and 29 is the smallest such number below the cycle length of 30.

A second example: shifting the pattern

A number leaves remainder 3 when divided by 4, and remainder 5 when divided by 7. What is it, mod 28?

List numbers that are $3 \pmod 4$: 3, 7, 11, 15, 19, 23, .... Check each against "remainder 5 mod 7": $3 \to 3$ (no), $7 \to 0$ (no), $11 \to 4$ (no), $15 \to 1$ (no), $19 \to 5$ (yes). So $N \equiv 19 \pmod{28}$, since $4 \times 7 = 28$. Notice the trick generalizes instantly — you never needed algebra, just an ordered walk down one list checking against the other condition.

Where this shows up beyond eggs

The reusable move is: a system of "leftover" constraints against coprime divisors collapses to one clue modulo their product. This is the same machinery behind why calendar-cycle puzzles ("this day of the week and this day of the month coincide every how-many years?") and hashing schemes that combine multiple small moduli for a larger effective range both have clean, unique-cycle answers. In quant interviews it resurfaces disguised as scheduling puzzles, cyclic-index problems, and any "when do these two periodic things line up again" question — recognize the shape and skip straight to combining remainders pairwise.