Determine sum mod p I want to calculate
$$
\sum_{k = 1}^{p-1} k^n \,\,\,\,\,\text{(mod $p$)}
$$
with the knowledge $n \not\equiv 0 $ (mod $p-1$), where $n \geq 1$ and $p$ is an odd prime.
 A: $\mathbb{Z}/(p\mathbb{Z})^*$ is a cyclic group (it is the multiplicative part of a finite field), hence all the non-zero remainders $\!\!\pmod{p}$ can be represented as $g^r$ for $r\in[1,p-1]$, with $g$ being one of the $\varphi(p-1)$ generators of $\mathbb{Z}/(p\mathbb{Z})^*$. In particular, for any $n$ which is not a multiple of $p-1$
$$ \sum_{k=1}^{p-1}k^n \equiv \sum_{r=1}^{p-1} g^{rn}\equiv \frac{g^{pn}-1}{g^n-1}-1\equiv\frac{g^n-1}{g^n-1}-1\equiv 0 \pmod{p}$$
where $\frac{1}{g^n-1}$ stands for the inverse of $g^n-1\pmod{p}$.
A: Suppose $n$ does not divide $p-1$. Then the map
$$x \mapsto x^n$$
from $\mathbb{F}_p^\times \to \mathbb{F}_p^\times$ is surjective, since $\mathbb{F}_p^\times$ is a cyclic group of order $p-1$. To see this, let $g$ be a generator of $\mathbb{F}_p^\times$. Then $g^n$ is still a generator of the group and is in the image. So in fact the map is bijective since it is between finite sets of same cardinality.
So, we have
$$
\sum_{k=1}^{p-1} k^n \equiv \sum_{k=1}^{p-1} k \pmod {p}
$$
and the last sum is zero when $p$ is an odd prime. To see this, pair off terms: this is
$$
\sum_{k=1}^{(p-1)/2} k + (p-k) \equiv \sum_{k=1}^{(p-1)/2} 0 \pmod p.
$$
