power sum divisible by prime $p>2$ is a prime and $p-1$ doesn't divide $n$. Prove that
$$1^n+2^n+3^n+\ldots +(p-1)^n \equiv 0 \pmod{p}$$
My solution so far: If $n$ is odd then 
\begin{align*}
1^n+2^n+3^n+\ldots +(p-1)^n &\equiv 1^n+2^n+3^n+\ldots +(-3)^n+(-2)^n+(-1)^n \\
&\equiv 1^n-1^n+2^n-2^n+\ldots +\left( \frac{p-1}2 \right)^n- \left( \frac{p-1}2 \right)^n\\
&\equiv 0
\end{align*}
How should I approach this problem, if $n$ is even?

For the values of $n$ such that $p-1$ does not divide $n$, we use the concept of a primitive root modulo $p$.  This is an integer between $1$ and $p – 1$ whose powers, taken $\mod p$, produce a rearrangement of the integers from $1$ to $p – 1$. If you know finite field theory, it might be familiar.
http://en.wikipedia.org/wiki/Primitive_root_modulo_n
Every prime number $p$ has at least one primitive root modulo $p$, $m$. So we rewrite the sum as:
$$m^n + (m^2)^n + ... +(m^{p-1})^n = m^n + (m^n)^2 + ... +  (m^n)^{p-1} = m^n \frac{(m^n)^{p-1}-1}{m^n-1}$$
Because $n$ is not a multiple of $p – 1$, the denominator is not zero (this is by group theory, the order of the multipicative group of integers modulo $p$ is $p-1$, so since $n$ is not a multiple of $p-1$, $m^n$ cannot be $1$ the identity of that group), while $m^n$ is within the multiplicative group of integers modulo $p$, so not divisible by $p$, hence when raised to $p-1$, it is equivalent to $1 \pmod p$ by Fermat's Little Theorem. So the numerator is $0$.
