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.

  • $\begingroup$ 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$ $\endgroup$ – Young May 1 '16 at 8:33
  • 1
    $\begingroup$ It is trivial if $k$ is odd. (By using mod) $\endgroup$ – N.S.JOHN May 1 '16 at 9:31
  • $\begingroup$ Did you try using the hint? $\endgroup$ – peter a g May 9 '16 at 2:31
  • $\begingroup$ 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. $\endgroup$ – coffeemath May 9 '16 at 2:32
  • 3
    $\begingroup$ 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. $\endgroup$ – 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<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.$

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

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

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

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

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.

  • $\begingroup$ You are awesome! This is magical!! $\endgroup$ – Subham Jaiswal May 23 '16 at 17:46
  • $\begingroup$ Ah! Sorry, for some reason I didn't notice your comment before. Thanks for the compliment. :) $\endgroup$ – awllower Jan 8 '17 at 8:49
  • $\begingroup$ 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? $\endgroup$ – 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$


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


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.