This will be reduced to $1^k+2^k+3^k+\cdots+(p-1)^k$ by Fermat Theorem. I know that the sum of the reduced residue system of $n$ is divisible by $n$. What I need to show, though, is that $1^k+2^k+3^k+\cdots+(p-1)^k$ is a reduced residue system of $p$. How to do so?
Is there any other methods to prove so?
Added
I thought of pairing elements such as $a$ and $p-a \equiv -a$ to cancelled out. But this works for odd $k$ only.