What is $1^k+2^k+\cdots+ (p-1)^k$ modulo $p$? (From Ireland and Rosen).

Question

I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks

Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and $-1\pmod{p}$ if $p-1\mid k$.

My work is leading where I didn't expect to go. Here I assume $p$ id odd. First, if $p-1\mid k$, then we can wrike $k=(p-1)j$ for some $j$. But then $$ 1^k+\cdots+(p-1)^k\equiv 1^{(p-1)j}+\cdots+(p-1)^{(p-1)j}\equiv \underbrace{1+\cdots+1}_{p-1\text{ times}}=\frac{(p-1)p}{2}\equiv 0\pmod{p} $$ since $p-1$ is even.

Secondly, I suppose $p-1\nmid k$. WLOG, I can assume $0<k<p-1$, Since if $k=(p-1)j+r$ with $0<r<p-1$, then $$ a^k\equiv a^{(p-1)j+r}\equiv a^r\pmod{p}. $$

Then if $g$ is a primitive root, $$ 1^k+\cdots+(p-1)^k=\sum_{i=1}^{p-1}(g^k)^i=\frac{g^k(1-g^{k(p-1)})}{1-g^k}. $$ Since $g$ is primitive, $p\nmid 1-g^k$, but $p\mid 1-g^{k(p-1)}$, so the above sum is again congruent to $0\pmod{p}$.

So in all cases, I get the sum is congruent to $0$ regardless. Have I messed up, or is there a typo? Thanks.

Answer 1

Let $g$ be a primitive root of $p$. Then $2,3,\dots,p-1$ are congruent, in some order, to $g,g^2, \dots,g^{p-2}$.

Thus our sum $S_k$ is congruent to $$1+g^{k}+g^{2k}+\cdots +g^{(p-2)k}\tag{$1$}$$ modulo $p$.

If $p-1$ divides $k$, then by Fermat's Theorem each term is congruent to $1$ modulo $p$. There are $p-1$ terms, so the sum is congruent to $-1$ modulo $p$.

Now suppose that $p-1$ does not divide $k$. Multiplying expression $(1)$ by $1-g^k$, we obtain $$(1-g^k)S_k\equiv 1-g^{(p-1)k}\equiv 0\pmod{p}.$$ Since $p-1$ does not divide $k$, and $g$ has order $p-1$, it follows that $1-g^k\not\equiv 0\pmod{p}$. It follows that $S_k\equiv 0\pmod{p}$.

Answer 2

In the case that $p-1\mid k$, you should have had $$\underbrace{1+\cdots+1}_{p-1\text{ times}}=p-1\equiv -1\bmod p.$$

Answer 3

Hint

If $p-1 \mid k$, then by Fermat Little Theorem $j^k \equiv 1 \pmod p$.

If $p-1 \nmid k$, then pick some $1 < j < p-1$ so that $j^k \ne 1 \pmod p$. Then

$$f(x)= j^kx$$

is a bijection from $\{ 1,2,.., p-1\}$ to $\{ 1,2,.., p-1\}$. This shows that

$$j^k(1^k+2^k+\cdots+(p-1)^k)=1^k+2^k+\cdots+(p-1)^k \pmod p$$

from where your claim follows..