Sums of powers modulo $p$

Question

I'm doing exercises in an elementary number theory book, and I'm asked to prove the claim, for prime $p$:

If $2^m\not\equiv 1\pmod{p}$, then
$1^m+2^m+\cdots +(p-1)^m\equiv 0\pmod{p}$

It is quite clear to me why this is true for odd $m$, but I don't see why it works when $m$ is even. For $m$ odd, everything cancels in pairs: $a^m+(p-a)^m\equiv 0$; great.

Looking at examples where $m$ is even, it appears to be true, even when $2^m\equiv 1$, as long as $m<p-1$, where it obviously fails. (See, for example, $p=17, m=8$.)

I observe that, in the even case, it suffices to examine the sum from $1$ to $\frac{p-1}{2}$, because the second half of the residue system just repeats this, and $0$ is the unique solution of $2x\equiv 0$.

So, can anyone give me a hint on this, and is the condition $2^m\not\equiv 1$ really the right condition? Thanks in advance for any insights.

Answer 1

Since the other two answers use material far beyond what’s necessary for the question, this question deserves a more elementary answer.

It isn’t explicitly stated in the question, but the claim is false for $p=2$ (since OP mentions $(p-1)/2$ they are likely aware of this already). So we assume $p$ to be odd, which we use many times in what follows.

Let $S = 1^m + 2^m + \cdots + (p-1)^m$ be the sum in question. Now consider $$2^m S = 2^m + 4^m + \cdots + (2p-2)^m.$$

We split this sum into the left and right halves

$$[2^m + 4^m + \cdots + (p-1)^m] \\ + [(p+1)^m + (p+3)^m+\cdots+(2p-2)^m],$$ which is congruent mod $p$ to

$$[2^m + 4^m + \cdots + (p-1)^m \\ + [1^m + 3^m + \cdots + (p-2)^m].$$

We quickly see that this is exactly the same sum as $S$ with the even and odd terms separated out. Thus $2^m S \equiv S \pmod p$, so that $(2^m-1)S$ is divisible by $p$. By assumption, the first factor is not divisible by $p$ so it must be $S$ that’s divisible by $p$.

There is absolutely no need for primitive roots or elaborate combinatorial identities here. Some basic group theory is lurking unspoken in the background, but we were able to complete the entire argument without even appealing to the existence of modular inverses! I think this answers the OP’s question of why the problem seems unnecessarily specific: specializing the problem to this extent affords a very elementary proof.

More generally, we can use this argument in other rings where there is an invertible multiplier $g$ such that $g^m-1$ is also invertible (note that we are free to have the sum include or exclude noninvertible indices). But this takes a little bit more sophistication to see that the action of multiplying by $g$ permutes the elements, whereas in the case of $g=2$ it resolves into just even and odd terms.

Answer 2

Let $g$ be a primitive root modulo $p$. Then $$1^m+2^m+\cdots+(p-1)^m\equiv 1+g^m+g^{2m}+\cdots+g^{(p-2)m}\pmod p.$$ If $g^m\equiv1\pmod p$ this is $\equiv -1\pmod p$. Otherwise it is $\equiv (g^{(p-1)m}-1)/(g^m-1)\equiv0\pmod p$. Now $g^m\equiv 1$ iff $(p-1)\mid m$. If $(p-1)\mid m$ then $2^m\equiv1\pmod p$ but not conversely.

Answer 3

Obviously, we have to investigate the sum only for $0\le m<p-1$, since $x^{p-1}\equiv1\pmod p$ for $1\le x\le p-1.$ We can easily show $$x^m=\sum^m_{k=1}a_{mk}\,(x)_k$$ for $m\ge1$, where $a_{mk}$ are integer coefficients and $(x)_k$ are falling factorials, $$(x)_k=\prod^{k-1}_{i=0}(x-i),$$ by induction over $m$, since $$(x)_k\cdot x=(x)_k\cdot (x-k + k)=(x)_{k+1}+k\,(x)_k.$$ Morevoer, we have $$(x+1)_{k+1}-(x)_{k+1}=(x+1)\,(x)_k-(x)_k\,(x-k)=(k+1)\,(x)_k,$$ and thus $$\sum^{p-1}_{x=1}x^m=\sum^m_{k=1}\frac{a_{mk}}{k+1}\,(p)_{k+1}$$ by telescoping, since $(1)_{k+1}=0$ for $k\ge1.$ This is essentially what @serg_1 suggested, just a bit more elaborate to show why this won't work for $m=p-1$. However, it shows that $$\sum^{p-1}_{x=1}x^m\equiv1\pmod p$$ with the natural condition $m\not\equiv0\pmod{p-1}$ instead of the unnatural (though sufficient) condition $2^m\not\equiv1\pmod p$, without any primitive root.
In the special case where $\gcd(m,p-1)=1$, the sum is $\equiv0\pmod p$ because the $x^m$ are just a permutation of the residue classes $1,2,\ldots,p-1$. Interestingly, this is true even in the case of a composite, squarefree modulus: $x\to x^k \pmod n$ is a permutation on $\mathbb{Z}_n$, for a positive integer $n$ iff $n$ is squarefree and $\gcd(k, \lambda(n)) = 1$, where $\lambda(n)$ denotes the Carmichael function (cf. this abstract).