# Value of $\sum_{i=1}^{p} i^k \pmod{p}$

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

-
$1^4 + 2^4 + 3^4 = 98 \neq 0 \pmod 3.$ –  Ragib Zaman Sep 16 '12 at 10:23
In stead of $k=p-1$ it's actually $k\mid (p-1)$. If $p=3, (3-1)\mid 4$ and $98 \equiv -1 \pmod 3$ –  lab bhattacharjee Sep 16 '12 at 10:36
@labbhattacharjee I think you meant $p-1 \mid k$, but I see the idea. Thanks. –  Ragib Zaman Sep 16 '12 at 10:36
Ya, sorry for the lapsus calami. –  lab bhattacharjee Sep 16 '12 at 10:37
Shouldn't the sum go up to $p-1$ only? if $k\neq 0$ it doesn't change anything and if $k=0$ it makes @labbhattacharjee's observation work. –  S4M Sep 16 '12 at 10:41

From Ribenboim's book,

Let $S=\sum j^k$ where $(j,m)=1$ and $1≤j<m$ 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).

-

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

-
$\phi$ is not bijective. Consider $k=2$ and $p=3$. $\phi(0) = 0,~\phi(1) = 1, ~ \phi(2) = 4 \pmod{3} = 1$. The condition on $k$ is that $gcd(p-1, k) = 1$, which does not work for even $k$. –  Karolis Juodelė Sep 16 '12 at 11:33
@KarolisJuodelė what I wrote is only true for $gcd(p-1,k)=1$, thank you for the correction. I will think of how to demonstrate it when it's not the case, I am interested by the problem. –  S4M Sep 16 '12 at 11:58
My counterexample was kind of bad as I touched the $k = p-1$ case. Still, $k = 2$ is never bijective as $1^2 = -1^2 = 1$. –  Karolis Juodelė Sep 16 '12 at 12:03
@KarolisJuodelė I have the counter example $k=3, p=7$. –  S4M Sep 16 '12 at 12:12
Proof. Let $\phi_k (x) = x^k$ and let $F$ be a finite field. For any $k$, let $kj = p-1$, so that $\phi_k \circ \phi_j = \phi_{p-1}$ is not bijective. If $\phi_k$ is bjective then $\phi_j(x) - 1$ is a polynomial with $p-1$ roots. Thus $j = p-1$ and $k = 1$. –  Karolis Juodelė Sep 16 '12 at 12:22