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!