Skip to main content
OlympiadHQ

Browse · harp

Print

imc

number theory intermediate

Problem

For how many positive integers isnot divisible by ? (Recall that is the greatest integer less than or equal to .)
(A)
(B)
(C)
(D)
Solution
Clearly, fails. Except for the special case of , equals either or . If it equals , this implies that , so their sum is clearly a multiple of , so this will always fail. If it equals , the sum of the three floor terms is , so it is never a multiple of . Thus, we are looking for all such that This implies that either or Let's analyze the first equation of these two. This equation is equivalent to the statement that there is a positive integer such that Analogously, the second equation implies that So our only that satisfy this condition are that divide or . Using the method to find the number of divisors of a number, we see that has divisors and has divisors. Their only common factor is , so there are positive integers that divide either or . Since the integer is a special case and does not count, we must subtract this from our , so our final answer is
Final answer
A