Bunuel wrote:
How many integers from 1 to 2003 inclusive have an odd number of distinct positive divisors?
(A) 100
(B) 75
(C) 50
(D) 46
(E) 44
If \(N=p_1^{q_1} \times p_2^{q_2} \times ... \times p_n^{q_n}\), where \(p_1, p_2, ..., p_n\) are distinct prime divisors, then the number of factors of \(N\) is \((1+q_1)(1+q_2)...(1+q_n)\)
If \(N\) has an odd number of distinct divisors, then \((1+q_1)(1+q_2)...(1+q_n)\) is odd, so \(q_1, q_2, ..., q_n\) are all even.
So, we simply count the number of integers from 1 to 2003 that these numbers are squared.
For example, \(1^2\) has only 1 positive divisors.
\(2^2\) has 3 positive divisors 1, 2, and 4.
\(3^2\) has 3 positive divisors 1, 3, and 9.
\(4^2=2^4=16\) has 5 positive divisors 1, 2, 4, 8, 16.
\(6^2 =2^2 \times 3^2=36\) has 9 positive divisors 1, 2, 3, 4, 6, 9, 12, 18, 36.
Note that \(44^2=1936\) and \(45^2=2025\), so these numbers are \(1^2, 2^2,..., 44^2\). There are 44 numbers like them.
The answer is E
In this solution, we count only squared number. What about other number is formed by even exponent like \(k^4, k^6, k^8,...\)?
Note that \(k^4=(k^2)^2\), and we've already counted \(k^2\). For example, counting \(2^4\) means counting \((2^2)^2=4^2\).
Also, \(k^6=(k^3)^2\). For example, counting \(3^6\) means counting \((3^3)^2=27^2\).
_________________