8
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Look up Newton's identities for elementary symmetric polynomials: en.m.wikipedia.org/wiki/Newton%27s_identities $\endgroup$
    – Berci
    Dec 7, 2020 at 11:07
  • $\begingroup$ @Berci Newton's identities do not hold over fields of positive characteristic. Do you think it can still be of help with this question? $\endgroup$
    – Levent
    Dec 7, 2020 at 11:16
  • 3
    $\begingroup$ 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. $\endgroup$
    – TravorLZH
    Dec 7, 2020 at 12:13

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .