Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A farmer counts the eggs in a basket. Taken two, three, four, five or six at a time, one egg is always left over. Taken seven at a time, none is left. The basket holds fewer than eggs. Find the least possible number of eggs and the only other possible number. Explain why the first five conditions collapse into one congruence.
With pairwise coprime moduli, a system has one solution modulo . Lift one congruence at a time:
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. modulo , and .
Plan. Turn the first five into one congruence, then lift.
Step 1. One congruence. is a multiple of each of , so of their lcm, . So .
Step 2. Modulo 7. , so , that is . The inverse of modulo is , so .
Step 3. The numbers. gives . The next is , which gives .
Step 4. The bound. The next value, , gives , which is too many. So exactly two numbers fit.
Check. , and .
Answer: the least number is , and the only other possible number is .
Watch out. The answers repeat every eggs, the lcm of all six moduli. Read the bound in the question before you list answers.
Log in to join the discussion.
Loading…