# Sums of powers below a prime

Given a prime $p$ and a natural number $k$, such that $k$ is not divisible by $p - 1$, prove that $\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p$.

I split the proof into two cases: one where $k$ is odd and another where it is even.

The case where $k$ is odd can be proven as follows:

$$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \pmod p$$

Since $k$ is odd each $(-i)^k = -i^k$, and will cancel with the positive $i$ leaving a zero. Therefore,

$$\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p \text{ if k is odd.}$$

I approached the case where $k$ is even in a similar fashion.

$$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \equiv 2(\sum_{i = 1}^{\frac{p - 1}{2}}i^k) \space \pmod p$$

Since $p$ is prime, we just need to prove that $\displaystyle\sum_{i = 1}^{\frac{p - 1}{2}}i^k \equiv 0 \pmod p$.

I was stumped after this, so I considered a counterexample, one where $k$ is divisible by $p - 1$. In that I considered a case where $p = 5, k = 8$:

$$1^8 + 2^8 + 3^8 + 4^8 \equiv 1 + 1 + 1 + 1 \space \pmod p$$

This and a few other cases led to the conjecture that all the numbers below $p$ have a mod cycle $(mod \space p)$ that is divisible by $p - 1$. I tested it with $p = 7$.

$2: 2, 4, {\color{red}1}$

$3: 3, 2, 6, 4, 5, {\color{red}1}$

$4: 4, 2, {\color{red}1}$

$5: 5, 4, 6, 2, 3, {\color{red}1}$

After this I was stuck. I couldn't see how this would help me solve the problem. And, more importantly, I couldn't prove my conjecture.

-
–  lab bhattacharjee Jul 2 '13 at 3:23
–  lab bhattacharjee Jul 2 '13 at 3:26

HINT:

As $i,1\le i\le p-1$ forms Reduced Residue System $\pmod p,$

and so does $g^r,$ for $0\le r\le p-2$ where $g$ is a primitive root of $p$

$$\text{So, }\sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\pmod p$$

$$\text{Now, }\sum_{0\le r\le p-2}(g^r)^k=\frac{(g^k)^{p-1}-1}{g^k-1}=\frac{(g^{p-1})^k-1}{g^k-1}$$

Using Fermat's Little Theorem, $g^{p-1}\equiv1\pmod p\implies (g^{p-1})^k\equiv1\pmod p\iff (g^{p-1})^k-1\equiv0\pmod p$

As $g$ is a primitive root of $p,\text{ord}_pg=p-1\implies g^k\not\equiv1\pmod p$ as $k$ is not divisible by $p-1$

$\implies (g^k-1,p)=1\implies \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$

$\implies \sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\equiv \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$

-

Let $b$ be any number relatively prime to $p$. Recall that the numbers $b, 2b, 3b, 4b, \dots, (p-1)b$ are a reduced residue class modulo $p$. This means that $b,2b,3b,\dots, (p-1)b$ travel, modulo $p$, through $1,2,3,\dots, p-1$ in some order.

It follows that $$b^k+(2b)^k+(3b)^k+\cdots +((p-1)b)^k \equiv 1^k+2^k+3^k +\cdots +(p-1)^k\pmod{p}\tag{1}$$ But $(ib)^k=b^ki^k$, so we can rewrite (1) as $$(b^k-1)\left(1^k+2^k+3^k+\cdots +(p-1)^k\right)\equiv 0\pmod{p}.\tag{2}$$

Let $b$ have order $p-1$ modulo $p$. So we are letting $b$ be a primitive root of $p$. Since $p-1$ does not divide $k$, we have $b^k \not\equiv 1\pmod{p}$. Then it follows from (2) that $1^k+2^k+3^k+\cdots (p-1)^k \equiv 0\pmod{p}$.

-

All nonzero numbers less than p are roots of $x^{p-1}=1$ (mod p). Thus, all the elementary symmetric polynomials in these number of order less than p-1 are zero (mod p), so any symmetric polynomial in these numbers of order less than p-1 must be zero (mod p).

-
Really neat! :) –  Rodrigo Jan 18 at 14:35