$1^n +2^n + \cdots +(p-1)^n \mod p =$?

Solution 1:

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$...

Solution 2:

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?

Solution 3:

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$?