4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this question may be relevant. $\endgroup$ – lulu Sep 26 '18 at 11:13
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.