I would appreciate if somebody could help me with the following problem:

Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?

closed as off-topic by user223391, mau, Ethan Bolker, rajb245, Parcly Taxel Feb 19 at 14:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, mau, Ethan Bolker, rajb245, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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
up vote 3 down vote accepted

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$

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!! – TheBox 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

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