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

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.

• this question may be relevant. – lulu Sep 26 '18 at 11:13

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.

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$$.

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$. Given such a $g$, it is easy to show that, modulo $p$, $$g,g^2,\cdots,g^{p-1}$$ are precisely the numbers $$1,2,\cdots,p-1,$$ in some order.

Thus $$1^d+2^d+\cdots+(p-1)^d\equiv 1+g^d+g^{2d}+\cdots+g^{(p-2)d}\pmod{p}.$$

Now, since $d\leq p-2$ it is clear that $$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$