If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ then $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$

If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ prove that $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$. Given hint: use primitive root.

This is a question on a practice final of mine. For $k$ being odd, it seems obvious (as the $\pm$ terms cancel out), but I cannot figure out how to do this for the general case.

Solution 1:

Below are six alternative approaches:

First, let $a$ be a number such that $\gcd(a,p)=1$ and $a^k\not\equiv1\pmod p,$ which exists as $k<p-1.$ Then denote the sum as $S:=\sum\limits_{l=1}^{p-1}l^k.$ So we find: $$a^k\cdot S\equiv\sum\limits_{l=1}^{p-1}(al)^k\pmod p.$$ Since $\{1\pmod p,\cdots,p-1\pmod p\}=\{al\pmod p\mid l=1,\cdots,p-1\},$ we conclude that $a^k\cdot S\equiv S\pmod p,$ and hence $S\equiv0\pmod p,$ as $a^k\not\equiv1\pmod p.$
$\square$

We might also use the Faulhaber's formula: $$\sum\limits_{l=1}^{p}l^k=\frac{1}{k+1}\sum\limits_{j=0}^k(-1)^j\binom{k+1}{j}B_jp^{k+1-j}\in\mathbb Q.$$ Now for $0\le k<p-1,$ we have $k+1<p$ is prime to $p,$ so is invertible modulo $p.$ Moreover, by Clausen - von Staudt Theorem, the prime divisors of denominators of $B_j$ are $\le j+1<p,$ and hence the denominators of $B_j$ are invertible modulo $p$ as well. Thus, by multiplying the Faulhaber's formula by $k+1$ and the denominators of $B_j,$ we find that $S\equiv\sum\limits_{l=1}^{p}l^k\pmod p$ is a polynomial in $p,$ and hence is divisible by $p.$
$\square$

The third approach is inspired by this answer. We define the operator $[z^k]$ as the coefficient of $z^k$ in a power series. Then $l^k=k![z^k]e^{lz}.$ Thus $$S=\sum\limits_{l=0}^{p-1}l^k=\sum\limits_{l=0}^{p-1}k![z^k]e^{lz}=k![z^k]\sum\limits_{l=0}^{p-1}e^{lz}=k![z^k]\frac{e^{pz}-1}{e^z-1}.$$ Hence it remains to compute the coefficients of $\frac{e^{pz}-1}{e^z-1}.$
Write $e^{pz}-1=\sum\limits_{j=1}^\infty (p^jz^j)/j!$ and $e^z-1=\sum\limits_{j=1}^\infty (z^j)/j!.$
Thus we see that $[z^k]\frac{e^{pz}-1}{e^z-1}$ is $\frac{1}{(k+1)!}$ times a polynomial in $p$ of zero constant term (one may use the Cauchy product). Then, for $0\le k<p-1,$ we deduce that $S$ is divisible by $p.$
$\square$

The fourth one is more algebraic: we work over $\mathbb F_p.$ We consider the polynomial $f(x):=x^{p-1}-1\in\mathbb F_p[x].$ By Fermat's little theorem, $f(x)$ has $p-1$ roots $1,\cdots,p-1\in\mathbb F_p.$ So $S=S_k$ is just the $k$-th power sum of the roots of $f(x).$ By Newton's identities, we have $$S_k=(-1)^{k-1}ke_k+\sum\limits_{i=1}^{k-1}(-1)^{k-1+i}e_{k-i}S_i,$$ where $e_k$ is the $k$-th elementary symmetric polynomial in the roots of $f(x).$ But $e_k$ is, up to the sign, the coefficient of $x^{p-1-k}$ in the polynomial $x^{p-1}-1.$ Thus, for $k=1,\cdots,p-2,$ we have $e_k=0.$ Therefore $S_k=0$ in $\mathbb F_p,$ i.e. $p\mid S_k.$
$\square$

The fifth uses only the basic algebraic properties about $\mathbb F_p.$
Consider the homomorphism $g:\mathbb F_p^*\rightarrow \mathbb{F}_p^*$ sending $a$ to $a^k.$ Then we have the isomorphism $\mathbb{F}_p^*/\operatorname{Ker}g\cong\operatorname{Im}g.$ Denote $\mid\operatorname{Im}g\mid=n$ which divides $p-1.$
We first show that $n\not=1.$ If $n=1,$ then $\mathbb{F}_p^*=\operatorname{Ker}g$ and hence $a^k=1, \forall a\in \mathbb{F}_p^*,$ which is impossible since a polynomial of degree $k$ can have at most $k$ roots in a field.
Then we choose $n$ representatives of $\mathbb{F}_p^*/\operatorname{Ker}g$ in $\mathbb{F}_p^*:\{a_1,\cdots,a_n\},$ so that $\mathbb{F}_p^*=\bigcup\limits_{i=1}^na_i\cdot\operatorname{Ker}g.$ Hence $$S_k=\sum\limits_{i=1}^n\sum\limits_{l\in\operatorname{Ker}g}(a_i\cdot l)^k=\sum\limits_{i=1}^nn\cdot a_i^k=n\cdot\sum\limits_{i=1}^ng(a_i)$$ Now $\{g(a_i)\mid i=1,\cdots,n\}=\operatorname{Im}g.$ Moreover, every element $l$ in $\operatorname{Im}g$ has order dividing $n,$ by Lagrange theorem, so each element in $\operatorname{Im}g$ is a root of $x^n-1.$ As that polynomial has no more than $n$ roots, it follows that $\operatorname{Im}g$ consists of the roots of $x^n-1$ in $\mathbb{F}_p.$ Therefore $S_k=n\cdot\sum\limits_{r^n-1=0}r,$ and hence $S_k$ is, up to a sign, equal to $n$ times the coefficient of $x$ in $x^n-1.$ But $n>1,$ thus $S_k=0$ in $\mathbb{F}_p,$ i.e. $p\mid S_k.$
$\square$

The sixth proof uses the forward-difference: for any function $f:\mathbb N\rightarrow\mathbb N$, define $T(f),\,\Delta(f):\mathbb N\rightarrow\mathbb N $ as $$ T(f)(n):=f(n+1),\,\forall n\in\mathbb N, $$ and $$ \Delta(f)(n):=f(n+1)-f(n)=(T-I)(f)(n),\,\forall n\in\mathbb N. $$

It is elementary to show that for any $n\in\mathbb N$ and $f:\mathbb N\rightarrow\mathbb N$, if for some $p\in\mathbb N$, $\Delta^{p+1}(f)(n)=0,\,\forall n\in\mathbb N$, then $$ f(n)=T^{n}(f)(0)={(\Delta+I)}^{n}(f)(0)=\sum_{k=0}^{p}\binom nk\cdot\Delta^{k}(f)(0). $$

For $k\in\mathbb N$, define $\delta_{k}:\mathbb N\in\mathbb N$ as $\delta_{k}(n)=\binom nk,\,\forall n\in\mathbb N$. Then the above means if $\Delta^{p+1}(f)(n)=0,\,\forall n\in\mathbb N$, then $$f=\sum_{i=0}^{p}\Delta^{i}(f)(0)\delta_{i}.$$

For $k\in\mathbb N$, define the function $p_{k}:\mathbb N\rightarrow\mathbb N$ as $p_{k}(n)=n^{k}$. It is quite easy to see that $\Delta^{k}(p_{k})=k!\,$, so $$ p_{k}=\sum_{i=0}^{k}\Delta^{i}(p_{k})(0)\delta_{i}. $$

As a consequence, \begin{align*} \sum_{n=1}^{p-1}p_{k}(n) &=\sum_{n=1}^{p-1}\sum_{i=0}^{k}\Delta^{i}(p_{k})(0)\binom ni\\ &=\sum_{i=0}^{k}\sum_{n=1}^{p-1}\Delta^{i}(p_{k})(0)\binom ni. \end{align*}

Now notice that $\binom ni=\binom{n+1}{i+1}-\binom{n}{i+1}$, and hence the above sum becomes telescopic, and we see $$ \sum_{n=1}^{p-1}p_{k}(n)=\sum_{i=0}^{k}\Delta^{i}(p_{k})(0)\binom{p}{i+1}. $$ Since by assumption each $i$ satisfies $i\leq k\leq p-2$, we know each $\binom p{i+1}$ is divisible by $p$. Therefore $\displaystyle\sum_{n=1}^{p-1}p_{k}(n)$ is divisible by $p$ as well.

Please point out any inappropriate points or doubts; hope this helps.

Solution 2:

Let $g$ be a primitive root of $p$, and let $S_k$ be our sum. Note that $g,g^2,g^3,\dots, g^{p-2}$ travel in some order, modulo $p$, through the numbers $2$ to $p-1$. It follows that $$S_k=1^k+2^k+3^k+\cdots +(p-1)^k\equiv 1^k+g^k+g^{2k}+g^{3k}+\cdots g^{(p-2)k}\pmod{p}.\tag{1}$$ Note that $$(1-g^k)(1+g^k+g^{2k}+g^{3k}+\cdots +g^{(p-2)k})=1-g^{(p-1)k}.$$ It follows that $$(1-g^k)S_k\equiv 1-g^{(p-1)k}\equiv 0\pmod{p}.$$ So $(1-g^k)S_k$ is divisible by $p$. However, $1-g^k$ is not divisible by $p$, and therefore $S_k$ is divisible by $p$.

Another way: We add a different proof, that may be less familiar. It does not use geometric series, only that $g$ has order $p-1$.

Note that $g,2g,3g,\dots,(p-1)g$ travel, modulo $p$, in some order, through $1,2,3,\dots,p-1$. It follows that $$1^k+2^k+3^k+(p-1)^k\equiv g^k(1^k+2^k+3^k+\cdots +(p-1)^k)\pmod{p}.$$ Thus $$S_k\equiv g^kS_k\pmod{p}.$$ But since $g^k\not\equiv 1\pmod{p}$, it follows that $S_k\equiv 0\pmod{p}$.

Solution 3:

As $(r,p)=1;1\le r\le p-1$

If $(p-1)|k, r^k\equiv 1\pmod p$

Else

If $a$ is a primitive root $\pmod p,$

$\{1,2,\cdots, p-2,p-1\};\{a^r, 0\le r\le p-1\}$ are the same set

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

$$\sum_{r=1}^{p-1}(a^r)^k=a^k\cdot\dfrac{(a^k)^{p-1}-1}{a^k-1}$$

Now $(a^k)^{p-1}=(a^{p-1})^k\equiv1^k\equiv?$

and $p\nmid(a^k-1)\iff(a^k-1,p)=1$ as $(p-1)\nmid k$