# Let \$p\$ be an odd prime and \$P(x)\$ a polynomial of degree \$p-2\$. If \$pmid P(n)+P(n+1)+…+P(n+p-1) forall n\$, must \$P\$ have integer coefficients?

I am stuck on this question from Zeit’s book The Art and Craft of Problem Solving.

Question

Let \$p\$ be an odd prime and \$P(x)\$ a polynomial of degree at most \$p-2\$.

If \$P(n)+P(n+1)+…+P(n+p-1)\$ is an integer divisible by \$p\$ for every integer \$n\$, must \$P\$ have integer coefficients?

Attempt

I think \$P\$ must have integer coefficients. Suppose \$P(x)=sum_{k=0}^{p-2} a_k cdot x^k\$. Define \$H(n)=P(n)+P(n+1)+…+P(n+p-1)\$. Then we can expand \$H(n)\$ into a polynomial \$H(n)=sum_{k=0}^{p-2} c_k cdot n^k\$, where each of the coefficients \$c_k\$ are some linear combination of \$a_k\$.

If \$c_i\$ is not an integer for some \$i\$, then I think by choosing some suitable \$n_i\$, we can cancel all denominators of \$c_j\$ where \$j neq i\$, while leaving \$c_i\$ still a fraction. Then \$H(n_i)\$ will be non-integer. But I don’t know how to prove this properly. The \$c_i\$ are already very complicated to express.

However, if \$c_i\$ is integer for all \$i\$, then I am stuck.

I also don’t know where to use the fact that \$pmid H(n)\$ for all \$n\$.

Thanks for the help!

All topic