Problem 19 · 2003 AMC 8
Hard
Number Theory
divisibilityfactorization
How many integers between 1000 and 2000 have all three of the numbers 15, 20, and 25 as factors?
Show answer
Answer: C — 3 integers.
Show hints
Hint 1 of 2
"Divisible by all three" collapses into one condition: divisible by their least common multiple. Find that one number first.
Still stuck? Show hint 2 →
Hint 2 of 2
Build the LCM from prime powers — take the highest power of each prime that appears across 15, 20, 25.
Show solution
Approach: collapse three conditions into one LCM, then count its multiples
- A number that has 15, 20, and 25 as factors must be a multiple of their LCM — so three conditions become one.
- Build the LCM from primes: 15 = 3·5, 20 = 2²·5, 25 = 5². Take the highest power of each prime seen: 2² × 3 × 5² = 4 × 3 × 25 = 300.
- Now count multiples of 300 strictly between 1000 and 2000: 1200, 1500, 1800 — that's 3.
- Worth keeping: LCM = highest power of each prime; GCD = lowest power. That prime-by-prime recipe never fails, even for three or more numbers at once.
Mark:
· log in to save