# Prove $1^r+2^r+.....\equiv 0\pmod p$ , given that p is odd prime and $0<r<p-1$

An exercise reads as follows: If $$p$$ is an odd prime and $$0 then prove that $$s=1^r+2^r+...(p-1)^r\equiv 0\mod p$$

I know one clever way to prove it is to use a primitive root $$g$$ and write the given sum as: $$g^r+g^{2r}+g^{3r} +...+g^{(p-1)r}$$ which is a geometric process easy to handle and deduce the result.

But I am looking for a more primitive way right now (suppose I know nothing about primitive roots). My thought is: the polynomial $$f=x^{p-1}-1$$ has $$p-1$$ roots distinct roots in the field $$\Bbb{Z_p}$$ so one can also write $$f= (x-1)(x-2)(x-3)...(x-(p-1))$$. By inspection of the coefficients of the 2 equal polynomials we get

$$t_1=1+2+3+...+(p-1)\equiv0 \mod p$$

$$t_2=1\cdot 2+1\cdot 3+...+(p-2)\cdot( p-1)\equiv 0 \mod p$$

$$t_3=1\cdot 2\cdot3+1\cdot 2\cdot4+...+(p-3)\cdot (p-2)\cdot(p-1)\equiv 0\mod p$$

and so on ....

now suppose $$r=2$$ then $$s=t^2_1 -2t_2$$, where we deduce that $$p$$ divides $$s$$

But how in general to compute $$s$$ by the $$t_i$$ mentioned above? Is there an algorithm for that? Thanks a lot.

• Look up Newton's identities for elementary symmetric polynomials: en.m.wikipedia.org/wiki/Newton%27s_identities Dec 7, 2020 at 11:07
• @Berci Newton's identities do not hold over fields of positive characteristic. Do you think it can still be of help with this question? Dec 7, 2020 at 11:16
• Since $p$ is an odd prime, it follows that $p-1$ is even, leaving us \begin{aligned} 1^r+2^r+\dots+(p-1)^r &=1^r+(p-1)^r+2^r+(p-2)^r+\dots+\left(p-1\over2\right)^r+\left(p+1\over2\right)^r \\ &\equiv1^r+(-1)^r+2^r+(-2)^r+\dots+\left(p-1\over2\right)^r+\left(1-p\over2\right)^r\pmod p \end{aligned} This implies when $r$ is odd this gets simplified into zero. Dec 7, 2020 at 12:13

There is another way to do this, I am not sure if this type of approach is what you had in mind:

Claim 1: Let $$H$$ be a subgroup [under multiplication] of $$(\mathbb{F}_p)^{\times}$$ that satisfies $$|H| \ge 2$$. Then $$\sum_{a \in H} a \equiv_p 0$$.

Indeed, we first note the following: For any $$a_0 \in H$$ the sets $$\{a; a \in H\}$$ and $$\{a_0a; a \in H\}$$ are the same. Thus for any $$a_0 \in H; a_0 \not = 1$$; we note the following:

$$a_0\sum_{a \in H} a = \sum_{a \in H} a_0a \equiv_p \sum_{a' \in H} a' =\sum_{a \in H} a.$$

However, as $$a_0 \not =1$$ the above implies that $$\sum_{a\in H} a$$ must be 0 mod $$p$$ and so Claim 1 follows. $$\surd$$

Now for each positive integer $$r$$, the set of $$r$$-th powers of $$(\mathbb{F}_p)^{\times}$$ form a subgroup $$H_r$$ of $$(\mathbb{F}_p)^{\times}$$, and for all $$a \in H_r$$ the number of solutions to $$x^r=a$$ is the same $$\frac{p-1}{|H_r|} < p-1$$ for all $$r [because $$(\mathbb{F}_p)^{\times}$$ is cyclic and so has an element of order $$p-1$$]. Thus $$|H_r| >1$$ and so

$$\sum_{x \in \mathbb{F}_p} x^r = 0^r + \frac{p-1}{|H_r|} \sum_{a \in H_r} a,$$

is indeed divisible by $$p$$ by Claim 1.

I do not know how in general to compute $$s$$ by your $$t_i$$'s, but here is a useful fact for your question.

Denote $$s_\ell:=\sum_{i=1}^{p-1}i^\ell$$, then one can prove that $$p^{r+1}-1=\sum^p_{k=2}((k)^{r+1}-(k-1)^{r+1})=\sum_{\ell=0}^r {r+1\choose \ell}s_\ell$$ by binomial theorem. It follows that \begin{align*} s=s_r&=\frac{1}{r+1}(p^{r+1}-1-\sum_{\ell=0}^{r-1} {r+1\choose \ell}s_\ell)\\ &=\frac{1}{r+1}(p^{r+1}-1-(p-1)-\sum_{\ell=1}^{r-1} {r+1\choose \ell}s_\ell)\\ &=\frac{1}{r+1}(p^{r+1}-p-\sum_{\ell=1}^{r-1} {r+1\choose \ell}s_\ell) \end{align*}

Relevant post:

Prove $$\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$$ for $$p$$ being an odd prime

HINT:

The polynomial $$1-t^{p-1}$$ decomposes $$\mod p$$ as $$1-t^{p-1}=(1-t)(1-2t)\cdots (1-(p-1)t)$$ so taking logarithmic derivative we get $$-\frac{t^{p-2}}{1-t^{p-1}} = \sum_{a=1}^{p-1} \frac{a}{1-a t}$$ Now consider the series expansion of both sides in $$\mathbb{F}_p[[t]]$$.