Problem 23 · 2006 AMC 8
Medium
Number Theory
chinese-remainder-by-listing
A box contains gold coins. If the coins are equally divided among six people, four coins are left over. If the coins are equally divided among five people, three coins are left over. If the box holds the smallest number of coins that meets these two conditions, how many coins are left when equally divided among seven people?
Show answer
Answer: A — 0.
Show hints
Hint 1 of 2
Two leftover conditions at once is hard to handle directly. List the numbers satisfying the rarer condition (leftover 4 from groups of 6), then just scan that short list for the other condition.
Still stuck? Show hint 2 →
Hint 2 of 2
"Leftover 4 when split into 6s" is the same as starting at 4 and stepping by 6. Walk that list and stop at the first number that also leaves 3 when split into 5s — the smallest match is your answer.
Show solution
Approach: list one condition, scan for the other
- Numbers leaving 4 when divided by 6: 4, 10, 16, 22, 28, … (start at 4, add 6 each time).
- Check each against "leftover 3 when divided by 5": 4→4, 10→0, 16→1, 22→2, 28→3 ✓. The first that works is 28.
- Now 28 ÷ 7 = 4 with remainder 0 — it splits evenly among seven people.
- Shortcut to notice: "leftover 4 out of 6" means 2 short of a full group, and "leftover 3 out of 5" also means 2 short of a full group. Being exactly 2 short of both 6 and 5 means 2 short of their LCM, 30 — so the number is 30 − 2 = 28 instantly, no listing needed. Spotting a common shortfall turns two conditions into one.
Another way — common shortfall → LCM:
- Leftover 4 of 6 is the same as being 2 below a multiple of 6; leftover 3 of 5 is being 2 below a multiple of 5.
- So the count is 2 below a common multiple of both: 2 below lcm(6,5) = 30, giving 28. Then 28 splits evenly by 7, remainder 0.
Mark:
· log in to save