Skip to main content
OlympiadHQ

Browse · harp

Print

smc

number theory intermediate

Problem

Let and let be the set of integers . The number of members of such that has remainder zero when divided by is:
(A)
(B)
(C)
(D)
(E)
Solution
Note that for all polynomials , . Proof: If , then . In the second equation, we can use the binomial expansion to expand every term, and then subtract off all terms that have a factor of or higher, since subtracting a multiple of will not change congruence . This leaves , which is , so . So, we only need to test when has a remainder of for . The set of numbers will repeat remainders, as will all other sets. The remainders are . This means for , is divisible by . Since is divisible, so is for , which is values of that work. Since is divisible, so is for , which is more values of that work. The values of will also generate solutions each, just like . This is a total of values of , for an answer of
Final answer
E