Art and Craft of problem solving, 7.6.15
"Let $p$ be an odd prime and $P(x)$ a polynomial of degree at most $p-2$. Prove that if $P$ has integer coefficients, then $P(n)+P(n+1)+…+P(n+p-1)$ is an integer divisible by $p$ for ever integer $n$."
I've reduced the problem down to showing that $1^d + 2^d + … + (p-1)^d$ is divisible by $p$ for all $d\leq p-2$. In the case where $d$ is odd this is straightforward but I can't seem to crack the even case. It may be that my approach is not the right one however, and there is another way. In particular, I have not been able to incorporate the primality of $p$.
Note there is a question on this website similar to mine, however, the other one is asking for a converse to what I am asking, and the two are not duplicates.
Best Answer
Your reduced problem is neatly solved by an application of primitive roots.
Let $g$ be a primitive root of $\mathbb{Z}/p\mathbb{Z}$, that is, an element whose order is $p-1$. The useful property we will exploit is that, modulo $p$, the numbers $$g,g^2,\cdots,g^{p-1}$$ are precisely $$1,2,\cdots,p-1,$$ in some order (this is left as an exercise for the interested reader).
Hence $$1^d+2^d+\cdots+(p-1)^d\equiv 1+g^d+g^{2d}+\cdots+g^{(p-2)d}\pmod{p}.$$
Since $d\leq p-2$ $$g^d\equiv a\pmod{p},$$ for some $a\in\{2,3,\cdots,p-1\}$.
Substituting $a$ into the last sum above $$1+a+\cdots+a^{p-2}=\frac{1-a^{p-1}}{1-a},$$ and so $$1^d+2^d+\cdots+(p-1)^d\equiv\frac{1-a^{p-1}}{1-a}\equiv0\pmod{p},$$ where the last equivalence follows from Fermat’s Little Theorem.
$\square$