Problem

There is a basket with a certain number of eggs.

If the eggs are taken from the basket two at a time, only one egg remains.

If the eggs are taken from the basket three at a time, only one egg remains.

If the eggs are taken from the basket four at a time, only one egg remains.

If the eggs are taken from the basket five at a time, only one egg remains.

If the eggs are taken from the basket six at a time, only one egg remains.

If the eggs are taken out seven at a time, no eggs remain.

How many eggs are in the basket?

[Assume the lowest integer solution]

Solution

This is an interesting Chinese remainder theorem problem that involves moduli that are not all mutually co-prime. The moduli 2, 3, 4, 6 are no co-prime, so we need to calculate the lowest common multiple: . Since the remainder of each congruence is 1, the above system can be reduced to .

The first two congruences in the reduced system have co-prime moduli, and they also share the same remainder, so Calculate the product of the moduli .

The solution of the Chinese remainder theorem prescribes that .

For this problem  where  are the modular inverses of each respective remainder, which can be solved systematically using the Euclidean algorithm. Calculation  There are 301 eggs in the basket.

Historical Note

This problem has a long history across Eurasia. Originally an Indian problem from the 7th century AD, the problem traveled along the Silk Road to Persia in the 10th century AD and eventually reaching Italy in the 13th century AD.