Today I Learned

April 5th

Today I learned a relatively clean proof of the fact that\[\sum_{n\in\FF_p^\times}n^k\equiv0\pmod p\]provided that $p-1\nmid k,$ from here . Quickly, we remark that $p-1\mid k$ implies that all terms are $1,$ so the sum comes out to $-1\pmod p.$ Anyways, we have the following.

The key trick is taken from the classical proof of Fermat's little theorem. Fix $a\in\FF_p^\times$ to be determined later, and we note that $\times_a:\FF_p^\times\to\FF_p^\times$ is a bijection. (E.g., $ak\equiv a\ell$ implies $k\equiv\ell,$ so the map is injective and therefore bijective because the sets are finite.) It follows that\[S_k:=\sum_{n\in\FF_p^\times}n^k\equiv\sum_{n\in\FF_p^\times}(an)^k\equiv a^kS_k\pmod p.\]Rearranging, it follows that $\left(a^k-1\right)S_k\equiv0\pmod p.$

Thus, it suffices to find some $a\in\FF_p^\times$ with $a^k-1\in\FF_p^\times$ so that we can multiply both sides of the equivalence by its inverse to conclude the needed $S_k\equiv0.$ To make this easy, we appeal to field structure. Quickly, note that it suffices to look at $k\pmod{p-1}$ by Fermat's little theorem, so it suffices to assume $k\in[1,p-1].$

Now, if there is no such $a,$ then\[x^k-1\in\FF_p[x]\]has $p-1$ roots, so it needs to have degree at least $k\ge p-1.$ (Note we have forced $k \gt 0,$ so the degree is well-defined.) But with $k\in[1,p-1],$ this can only happen provided that $k=p-1.$ So when $k\ne p-1,$ we see there must be some $a\in\FF_p^\times$ with $a^k-1\not\equiv0,$ and we're done. $\blacksquare$

This proof is truly very clever. We attempt to motivate it but will mostly fail. The proof that I'm used to (and consider fairly motivated) is to fix a generator $g\in\FF_p^\times$ so that\[S_k:=\sum_{n\in\FF_p^\times}n^k\equiv\sum_{n=0}^{p-2}g^{nk}.\]So we see that this is a geometric series. If one is relatively mindless as I am, then we just note directly that, for $(p-1)\nmid k,$\[S_k\equiv\frac{g^{(p-1)k}-1}{g^k-1}\equiv0\]by using the geometric sum formula and then Fermat's little theorem. $\blacksquare$

This direct approach is potentially problematic because we have to check that the geometric sum formula actually holds. Well, we just note that\[g^kS_k=\sum_{n=0}^{p-2}g^{(n+1)k}\equiv\sum_{n=0}^{p-2}g^{nk}\equiv S_k,\]and surely $g^k\not\equiv1\pmod p,$ so we must have $S_k\equiv0.$ (This is the same idea as in orthogonality of characters.) But looking at this line, there really is no reason to use $g$: we could take any $a=g^\bullet\in\FF_p^\times$ and still have\[a^kS_k=\sum_{n=0}^{p-2}g^{(n+\bullet)k}\equiv\sum_{n=0}^{p-2}g^{nk}\equiv S_k.\]For that matter, we don't even need the generator at this point, for $\times_a$ is a permutation of $\FF_p^\times$ anyways, and we can throw out all of the machinery from earlier, as was done in the original proof.

Of course, there is actually a legitimate reason to use the generator $g$ to do the multiplication $g^k.$ Namely, $g$ is guaranteed to have $g^k\not\equiv1$ for $(p-1)\nmid k,$ and not just any $a$ will do. I am under the impression that it is in general not trivial to find an $a$ for which $a^k\not\equiv1$; the details I provide appeal to Lagrange's theorem to say that some $a$ exists.

We remark that we need some kind of appeal to $\FF_p$'s field structure because there are monsters lurking here: we can of course generate groups for which $x^k=e$ has many more than $k$ solutions, so we need to use something more than the multiplicative structure here.

Even though we have removed generators, I don't actually think it's particularly easy to generalize this. Namely, we want to say $\left(a^k-1\right)S_k=0$ implies $a^k-1=0$ or $S_k=0$ at one point in the proof, so we need to be an integral domain. Additionally, we need some kind of finiteness condition in order to make the sum of units make sense, and finite plus integral domain already implies field.