# 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 five 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 following 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$

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