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. 
 A: 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}$.
A: 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$
A: 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).
