Prove $1^r+2^r+.....\equiv 0\pmod p$ , given that p is odd prime and $0An exercise reads as follows:
If $p$ is an odd prime and $0<r<p-1$ 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.
 A: 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<p-1$ [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.
A: 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
A: 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]]$.
