If $p$ is an odd prime and $k$ an integer with $0
If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ prove that $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$. Given hint: use primitive root.
This is a question on a practice final of mine. For $k$ being odd, it seems obvious (as the $\pm$ terms cancel out), but I cannot figure out how to do this for the general case.

Let $g$ be a primitive root of $p$, and let $S_k$ be our sum. Note that $g,g^2,g^3,\dots, g^{p-2}$ travel in some order, modulo $p$, through the numbers $2$ to $p-1$. It follows that
$$S_k=1^k+2^k+3^k+\cdots +(p-1)^k\equiv 1^k+g^k+g^{2k}+g^{3k}+\cdots g^{(p-2)k}\pmod{p}.\tag{1}$$
Note that 
$$(1-g^k)(1+g^k+g^{2k}+g^{3k}+\cdots +g^{(p-2)k})=1-g^{(p-1)k}.$$
It follows that
$$(1-g^k)S_k\equiv 1-g^{(p-1)k}\equiv 0\pmod{p}.$$
So $(1-g^k)S_k$ is divisible by $p$. However, $1-g^k$ is not divisible by $p$, and therefore $S_k$ is divisible by $p$.
Another way: We add a different proof, that may be less familiar. It does not use geometric series, only that $g$ has order $p-1$.
Note that $g,2g,3g,\dots,(p-1)g$ travel, modulo $p$, in some order, through $1,2,3,\dots,p-1$. It follows that
$$1^k+2^k+3^k+(p-1)^k\equiv g^k(1^k+2^k+3^k+\cdots +(p-1)^k)\pmod{p}.$$
Thus 
$$S_k\equiv g^kS_k\pmod{p}.$$
But since $g^k\not\equiv 1\pmod{p}$, it follows that $S_k\equiv 0\pmod{p}$.
