Determine sum mod p

Question

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.

Answer 1

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

Answer 2

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