For any positive number $k$, find the value of $1^k + 2^k + 3^k+...+(p-1)^k$(mod $p$)

Question

For any positive number $k$, find the value of

$1^k + 2^k + 3^k+...+(p-1)^k$(mod $p$) and prove that your answer is correct. A Little confused about this problem. Any help? Would love to see a solution for this.

Thank you.

Answer 1

If $g$ is a primitive root,

$S:\{s, 1\le s\le p-1\}, T:\{g^r\pmod p, 1\le r\le p-1\}$ will be the same set

$$\implies\sum_{s=1}^{p-1}s^k\equiv\sum_{r=1}^{p-1}(g^r)^k\equiv \sum_{r=1}^{p-1}(g^k)^r\pmod p$$

If $(p-1)\mid k, g^k\equiv1\pmod p $ $$ \sum_{r=1}^{p-1}(g^k)^r\equiv \sum_{r=1}^{p-1}1^r\pmod p\equiv p-1\equiv-1$$

Else $g^k\not\equiv1\pmod p\iff (g^k-1,p)=1$ $$ \sum_{r=1}^{p-1}(g^k)^r=g^k\frac{(g^k)^{p-1}-1}{g^k-1}=\frac{(g^p)^k-g^k}{g^k-1}\pmod p$$

As $g^p\equiv g\pmod p,(g^p)^k\equiv g^k,$

$$ \sum_{r=1}^{p-1}(g^k)^r\equiv\frac{g^k-g^k}{g^k-1}\equiv0\pmod p$$ as $ (g^k-1,p)=1$