Fix a prime number . Let be integers no two of which have their difference divisible by . Let be nonnegative integers such that is divisible by . Suppose that for all integers , the quantity
is divisible by . Prove that each of must be divisible by .
, 2009
Solution
We first prove that is congruent to one of modulo . We rephrase the hypothesis in terms of modular arithmetic: If , then
By Fermat's little theorem, there is no harm in shifting by multiples of , so we may assume are elements of the set . If , then the condition forces . In this case, the polynomial has degree at most (since it is the difference of two monic polynomials of degree ), but modulo it has at least distinct roots (namely the values of other than ). The only ways to avoid a contradiction are either to have or to have the polynomial be identically zero modulo . The former gives and we are done. The latter forces by unique factorization of polynomials modulo , so we are again done.
If on the other hand , then we also have
for all not congruent to modulo . If , we are done; otherwise, the fact that forces , so . Thus the previous paragraph implies either or .
By symmetry, each of , , is congruent to one of , , modulo . Because (mod ) and , the only possibilities (up to permutations) are (mod ) or (mod ). However, the latter implies that (mod ) for all (mod ), which is impossible as soon as there is at least one such (which is true since ). This contradiction leaves only the possibility (mod ), proving the desired result.