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\).

_________________

Actual LSAT CR bank by Broall

How to solve quadratic equations - Factor quadratic equations

Factor table with sign: The useful tool to solve polynomial inequalities

Applying AM-GM inequality into finding extreme/absolute value

New Error Log with Timer