$1^n +2^n + \cdots +(p-1)^n \mod p =$? Calculate for every positive integer $n$ and for every prime $p$ the expression 
$$1^n +2^n + \cdots +(p-1)^n \mod p$$

I need your help for this. I don't know what to do, but I'll show you what I know.


*

*Wilson's theorem

*The identity $X^p-X = \prod_{a \in \mathbb{F}_p-1}(X-a)$

*$\exists a \in \mathbb{Z}, \ a^2 \equiv -1 \mod p \qquad \iff \qquad p \equiv 1 \mod 4$
Now can you please provide me a hint?
 A: Hint: If $a^n \equiv 1 \pmod{p}$ for all $1 \leq a \leq p-1$ you know what the sum is.
Otherwise, if $a^n \neq 1 \pmod{p}$ for some $a$, then use the fact that $\{ a, 2a, 3a, .., (p-1)a \} = \{1,2,3,.., p-1\} \pmod{p}$. Thus
$$ 1^n +2^n + \cdots +(p-1)^n =a^n +(2a)^n + \cdots +[(p-1)a]^n \\
 = a^n \left( 1^n +2^n + \cdots +(p-1)^n  \right)  \pmod{p}$$
You also need to figure out for which $n$ you have $a^n \equiv 1 \pmod{p}$ for all $1 \leq a \leq p-1$...
A: From Fermat's little theorem, $x^{p-1}-1=0 \mod p$. From Vieta, this means that all the elementary symmetric polynomials in the x's of order less than p-1 must equal zero mod p. Thus any symmetric polynomial in the x's of order less tha p-1 must equal zero mod p. Is it really that simple, or am I missing something? 
A: Hint:
Consider the reordered sum:
$$1^n+(p-1)^n+2^n+(p-2)^n+...+\left({p-1\over2}\right)^n+\left({p+1\over2}\right)^n$$
For $p=2$, the sum resolves to $1^n$.  To see other values it would take on, assume $p\gt 2$.
If $n=1$, then the sum is the well-known binomial $\binom{p-1}2={(p-1)(p-2)\over 2}\equiv 1\mod p$.  This should be a good start for induction or direct proof for odd $n$.  Can you analyze the sum further and complete it for even $n$?
A: Take the group $G=(\mathbb{Z}_{p},\cdot)$ with the multiplication.
Since $p$ is prime then the order of $G$ is $p-1$.
Then  using $n=k(p-1)$ and $p-1=-1 \pmod p$.
$1^n +2^n +...+(p-1)^n=1+1+...+1=p-1=-1 \pmod p$
A: I don't see the simple answer plainly stated so I will state it here. For $p=2$, the only term in the sum is $1^n$ which is identified in a previous answer as $\equiv 1 \bmod 2$, but for consistency with the larger scheme of things, might better be stated as $\equiv -1 \bmod 2$
For odd $p$ and odd $n$, there are an even number (i.e., $p-1$) of addends, and the sum may be arranged as $1^n+(-1)^n+2^n+(-2)^n+\dots \equiv 0 \bmod p$
If $n$ is even, and if $(p-1)\mid n$, then every addend is a $(p-1)$ power of an integer, so every addend is $\equiv 1 \bmod p$ and the $(p-1)$ addends sum to $(p-1)\equiv -1 \bmod p$
If $n$ is even, and $p\equiv 1 \bmod 4$, and if $(p-1)\not \mid n$, then since quadratic residues in this case come in pairs $a, (p-a)$, the sum is $\equiv 0 \mod p$
If $n$ is even, and $p\equiv 3 \bmod 4$, and if $(p-1)\not \mid n$, I am without a proof, but empirically for several small primes, the sum is $\equiv 0 \mod p$
Overall, if $(p-1)\mid n$, the sum $\equiv -1 \bmod p$; otherwise, the sum $\equiv 0 \bmod p$
