4
$\begingroup$

I found a statement that $\sum \limits_{i=1}^{p} i^k \equiv \begin{cases} -1 && (p-1) \mid k \\ 0 && \text{otherwise}\end{cases} \pmod{p}$ for a prime $p$ and positive integer $k$. The result is obvious when $k$ is odd or equals $p-1$ but I can't prove it for all even values of $k$.

  • 0
    @S4M, The original statement was about any finite fields. I specialized it to $\pmod{p}$ and left the $p$ for $0$.2012-09-16

2 Answers 2

1

From Ribenboim's book,

Let $S=\sum j^k$ where $(j,m)=1$ and $1≤j where m is any natural number.

Let $ag\equiv bg\pmod m$ where $1\leq a\leq b\leq m$ and $(g,m)=1$

$\implies m\mid g(b-a)\implies m|(b-a)$ as $(g,m)=1$

But $m∤(b-a)$ as $1\leq a\leq b\leq m$, so, $ag≢bg\pmod m$.

So, the sets of reduced residue classes ${g, 2g, . . . , (m − 1)g}$ and ${1, 2, . . . , (m − 1)}$ are the essentially same only in some different order.

Then $g^kS ≡\sum(gj)^k ≡\sum j^k≡S \pmod m.$

Hence $(g^k−1)S ≡ 0 \pmod m$.

So, $m\mid S$ if $k ∤ ord_mg \implies g^k ≢ 1 \pmod m$

If $g$ is so chosen that o$rd_mg =\phi(m)$ i.e., if $g$ be a primitive root modulo $m$(assuming $m$ has at least one), then $m\mid S$ if $k ∤ \phi(m) \implies g^k ≢ 1 \pmod m$.

If $m$ becomes prime $p,\phi(m)=\phi(p)=p-1$ and all primes have primitive root(s).

0

If $p-1|k$, it's obvious due to Fermat's little theorem.

If not, let's start $k=1$. We have $\displaystyle\sum_{i=1}^p i^k = p + \sum_{i=1}^{p-1}i = 1 + (p-1) + 2+(p-2)+\dots + E(p/2)-1 + E(p/2)+1 = 0\mod p$.

In the general case (still, when $p-1$ doesn't divide $k$), we have the function $\varphi(i) = i^k\mod p$ that is a bijection of $\mathbb{[}1,p-1\mathbb{]}$. Indeed, if we could find $i\neq j \in \mathbb{[}1,p-1\mathbb{]}$ such as $i^k = j^k\mod p$, we would have $i-j$ that would be a divisor or $p$ which is impossible as $p$ is prime. We can then rewrite $\displaystyle\sum_{i=1}^{p-1}i^k$ as $\displaystyle\sum_{i=1}^{p-1}j_{i,k}$ where $j_{i,k} = i^k = \varphi(i)$, and since $\varphi$ is bijective, $\varphi([1,p-1] =[1,p-1]$, and so the sum is also equal to $\displaystyle\sum_{i=1}^{p-1} i = 0\mod p$.

  • 0
    @KarolisJuodelė clever! thanks for that, I really learnt something.2012-09-16