# 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.

• I find $k=1,2,3$ $$\frac{1}{2} (p-1) p,\frac{1}{6} (p-1) p (2 p-1),\frac{1}{4} (p-1)^2 p^2$$always a multiple of $p$ – Young May 1 '16 at 8:33
• It is trivial if $k$ is odd. (By using mod) – N.S.JOHN May 1 '16 at 9:31
• Did you try using the hint? – peter a g May 9 '16 at 2:31
• In the title, suggest you say "Prove for $p$ an odd prime..." to make it match with how the question is asked in the body of the post. Also include $0<k<p-1$ there for the same reason. – coffeemath May 9 '16 at 2:32
• The important thing is that if $g$ is a primitive root then $g^1,g^2,\dots, g^{p-1}$ are congruent to $1,2,\dots, p-1$ in some order. So modulo $p$ we can write our sum as a geometric progression. – André Nicolas May 9 '16 at 2:44

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}$.

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 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 we have $$k+1 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 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 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.

• You are awesome! This is magical!! – Subham Jaiswal May 23 '16 at 17:46
• Ah! Sorry, for some reason I didn't notice your comment before. Thanks for the compliment. :) – awllower Jan 8 '17 at 8:49
• I do not understand the reason to down-vote. Per chance I did something inappropriate in this answer, or is there anything I can improve upon? Care to point it out? – awllower Mar 31 '19 at 7:41

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$