Problem:
For how many integers between and , inclusive, is
an integer? (Recall that .)
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let
First, note that is an integer when . Next, observe that if is prime, then is not an integer because the numerator has factors of but the denominator has such factors. Note also that is not an integer, because the numerator, , has factors of , whereas the denominator, , has factors of . Therefore for , in order for to be an integer, a necessary condition is that be composite and greater than . The following argument shows that this condition is also sufficient.
First note that
If , where and are distinct positive integers greater than , then is an integer because both and appear as factors in . Otherwise for some odd prime . In this case , so has at least two factors of and again is an integer.
Now the number
is an integer because this expression counts the number of ways to separate objects into groups of size without regard to the ordering of the groups (which accounts for the extra factor of in the denominator).
By combining the previous two paragraphs, it follows that
is an integer if and only if or is composite and greater than . Thus the answer is minus minus the number of primes less than or equal to , which is .
The problems on this page are the property of the MAA's American Mathematics Competitions