How many positive perfect squares less than are divisible by ?
- A)
- B)
- C)
- D)
- E)
Answer
A
Key insight
A square is a multiple of 5 only when the number squared is a multiple of 5. Count 5, 10, 15, and so on while the square stays below 2023.
Solution
- First decide which squares are divisible by . Try a few: and are, but and are not. Since is prime, can only divide if it divides itself. So we want the squares of
- Next find where the squares stop being less than . We know and .
- is just above , so is not allowed. The last one that works is .
- List them: . Their squares are all below and all divisible by .
- That is squares.
The answer is .
Why this works
A prime number divides a square only when it divides the number being squared, so the question about squares turns into a question about multiples of . The only tricky part is the cutoff: misses by just , and that single case decides between (A) and (B). Always check the last case by hand.
The trap
Counting 45 as well. But 45 squared is 2025, which is just over 2023, and that gives the wrong answer 9.
Concise solution
Because is prime, divides exactly when divides . So we need to count positive multiples of whose squares are below .
Since and , the roots allowed are . The multiples of in this range are , which is numbers.
Their squares are , all below and all divisible by .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 1: Integers: The Basics
- Introduction to Number Theory, Chapter 2: Primes and Composites
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Techniques
Bound the quantity above/below or estimate to pin it down · Set up the equation/formula and compute; no special trick needed