Sums of powers below a prime

Solution 1:

Let $b$ be any number relatively prime to $p$. Recall that the numbers $b, 2b, 3b, 4b, \dots, (p-1)b$ are a reduced residue class modulo $p$. This means that $b,2b,3b,\dots, (p-1)b$ travel, modulo $p$, through $1,2,3,\dots, p-1$ in some order.

It follows that $$b^k+(2b)^k+(3b)^k+\cdots +((p-1)b)^k \equiv 1^k+2^k+3^k +\cdots +(p-1)^k\pmod{p}\tag{1}$$ But $(ib)^k=b^ki^k$, so we can rewrite (1) as $$(b^k-1)\left(1^k+2^k+3^k+\cdots +(p-1)^k\right)\equiv 0\pmod{p}.\tag{2}$$

Let $b$ have order $p-1$ modulo $p$. So we are letting $b$ be a primitive root of $p$. Since $p-1$ does not divide $k$, we have $b^k \not\equiv 1\pmod{p}$. Then it follows from (2) that $1^k+2^k+3^k+\cdots +(p-1)^k \equiv 0\pmod{p}$.

Solution 2:

HINT:

As $i,1\le i\le p-1$ forms Reduced Residue System $\pmod p,$

and so does $g^r,$ for $0\le r\le p-2$ where $g$ is a primitive root of $p$

$$\text{So, }\sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\pmod p$$

$$\text{Now, }\sum_{0\le r\le p-2}(g^r)^k=\frac{(g^k)^{p-1}-1}{g^k-1}=\frac{(g^{p-1})^k-1}{g^k-1}$$

Using Fermat's Little Theorem, $g^{p-1}\equiv1\pmod p\implies (g^{p-1})^k\equiv1\pmod p\iff (g^{p-1})^k-1\equiv0\pmod p$

As $g$ is a primitive root of $p,\text{ord}_pg=p-1\implies g^k\not\equiv1\pmod p$ as $k$ is not divisible by $p-1$

$\implies (g^k-1,p)=1\implies \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$

$\implies \sum_{1\le i\le p-1}i^k\equiv\sum_{0\le r\le p-2}(g^r)^k\equiv \frac{(g^{p-1})^k-1}{g^k-1}\equiv0\pmod p$