Prove $P(n)+P(n+1)+...+P(n+p-1)$ is divisible by $p$

Question

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.

Answer 1

More generally, let $f_d\in\mathbb{F}_p[x]$ be the polynomial $$f_d(x):=x^d+(x+1)^d+(x+2)^d+\ldots+(x+p-1)^d\,,$$ for $d\in\{0,1,2,\ldots,p-1\}$. We have $$f_d(0)=f_d(1)=f_d(2)=\ldots=f_d(p-1)\,.$$ Thus, $f_d(x)-f_d(0)$ is a polynomial of degree at most $d$ divisible by the degree-$p$ polynomial $x(x-1)(x-2)\cdots(x-p+1)$. This is possible only if $f_d(x)-f_d(0)$ is the zero polynomial, or equivalently, $f_d(x)$ is a constant polynomial. How does this help? Well, you can take the derivative of $f_d(x)$ and get $$f'_d(x)=d\,f_{d-1}(x)\text{ for }d=1,2,\ldots,p-1\,.$$ Since $f_d(x)$ is constant, $f'_d(x)=0$, whence $$f_{d-1}(x)=0\,,$$ as $d\not\equiv 0\pmod{p}$. This shows that $$x^d+(x+1)^d+(x+2)^d+\ldots+(x+p-1)^d\equiv 0\text{ for }d=0,1,2,\ldots,p-2\,.$$ In particular, plugging in $x:=0$, you obtain your required result.

Answer 2

The image $H$ of the map $x \mapsto x^d$ is a subgroup of $U(p)$ and so is cyclic. Let $m$ be the order $H$. Then $H$ is the set of solutions of $x^m=1$ and so the elements of $H$ sum to $0$. Finally, $x^d=y^d$ iff $x=uy$ with $u^d=1$ and so the elements $1^d, 2^d, \dots, (p-1)^d$ can be grouped in groups of size $m$.

Answer 3

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$