Problem 15 · AMC 8 Stretch
Core
Number Theory
logical-reasoningpattern-recognition
Find the smallest whole number \(n\) that leaves a remainder of \(1\) when you divide it by each of \(2, 3, 4, 5, 6, 7, 8, 9\).
Show answer
Answer: 2521
Show hints
Hint 1 of 4
If \(n\) leaves remainder \(1\) for all those divisors, what can you say about \(n - 1\)? It must divide evenly by all of them.
Still stuck? Show hint 2 →
Hint 2 of 4
So \(n - 1\) is a common multiple of \(2, 3, 4, 5, 6, 7, 8, 9\). The smallest such number is their least common multiple (LCM).
Still stuck? Show hint 3 →
Hint 3 of 4
Many of these are 'covered' by others. If a number is divisible by \(8\), it's automatically divisible by \(4\) and \(2\). If divisible by \(9\), it's divisible by \(3\). The numbers you really need are \(5, 7, 8, 9\).
Show solution
Approach: Reduce to an LCM by looking at n minus 1
- If \(n\) leaves remainder \(1\) when divided by each of \(2\) through \(9\), then \(n - 1\) divides evenly by all of them. So \(n - 1\) is their least common multiple.
- Many divisors are redundant: divisibility by \(8\) covers \(4\) and \(2\); by \(9\) covers \(3\); by \(2\) and \(3\) covers \(6\).
- The ones that really matter are \(5, 7, 8, 9\): \(\text{LCM} = 5 \times 7 \times 8 \times 9 = 2520\).
- So \(n - 1 = 2520\), giving \(n = 2521\).
Mark:
· log in to save