Fdtxjr

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.

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)^kequiv 1^k+g^k+g^2k+g^3k+cdots g^(p-2)kpmodp.tag1$$
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_kequiv 1-g^(p-1)kequiv 0pmodp.$$
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)^kequiv g^k(1^k+2^k+3^k+cdots +(p-1)^k)pmodp.$$
Thus
$$S_kequiv g^kS_kpmodp.$$
But since $g^knotequiv 1pmodp$, it follows that $S_kequiv 0pmodp$.

Below are five alternative approaches:

First, let $a$ be a number such that $gcd(a,p)=1$ and $a^knotequiv1pmod p,$ which exists as $k<p-1.$ Then denote the sum as $S:=sumlimits_l=1^p-1l^k.$ So we find:
$$a^kcdot Sequivsumlimits_l=1^p-1(al)^kpmod p.$$
Since $1pmod p,cdots,p-1pmod p=alpmod pmid l=1,cdots,p-1,$ we conclude that $a^kcdot Sequiv Spmod p,$ and hence $Sequiv0pmod p,$ as $a^knotequiv1pmod p.$

$square$

We might also use the Faulhaber's formula: $$sumlimits_l=1^pl^k=frac1k+1sumlimits_j=0^k(-1)^jbinomk+1jB_jp^k+1-jinmathbb Q.$$ Now for $0le 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 $Sequivsumlimits_l=1^pl^kpmod 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=sumlimits_l=0^p-1l^k=sumlimits_l=0^p-1k![z^k]e^lz=k![z^k]sumlimits_l=0^p-1e^lz=k![z^k]frace^pz-1e^z-1.$$ Hence it remains to compute the coefficients of $frace^pz-1e^z-1.$

Write $e^pz-1=sumlimits_j=1^infty (p^jz^j)/j!$ and $e^z-1=sumlimits_j=1^infty (z^j)/j!.$

Thus we see that $[z^k]frace^pz-1e^z-1$ is $frac1(k+1)!$ times a polynomial in $p$ of zero constant term (one may use the Cauchy product). Then, for $0le 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-1inmathbb F_p[x].$ By Fermat's little theorem, $f(x)$ has $p-1$ roots $1,cdots,p-1inmathbb 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-1ke_k+sumlimits_i=1^k-1(-1)^k-1+ie_k-iS_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. $pmid S_k.$

$square$

The following uses only the basic algebraic properties about $mathbb F_p.$

Consider the homomorphism $g:mathbb F_p^*rightarrow mathbbF_p^*$ sending $a$ to $a^k.$ Then we have the isomorphism $mathbbF_p^*/operatornameKergcongoperatornameImg.$ Denote $midoperatornameImgmid=n$ which divides $p-1.$

We first show that $nnot=1.$ If $n=1,$ then $mathbbF_p^*=operatornameKerg$ and hence $a^k=1, forall ain mathbbF_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 $mathbbF_p^*/operatornameKerg$ in $mathbbF_p^*:a_1,cdots,a_n,$ so that $mathbbF_p^*=bigcuplimits_i=1^na_icdotoperatornameKerg.$ Hence $$S_k=sumlimits_i=1^nsumlimits_linoperatornameKerg(a_icdot l)^k=sumlimits_i=1^nncdot a_i^k=ncdotsumlimits_i=1^ng(a_i)$$
Now $g(a_i)mid i=1,cdots,n=operatornameImg.$ Moreover, every element $l$ in $operatornameImg$ has order dividing $n,$ by Lagrange theorem, so each element in $operatornameImg$ is a root of $x^n-1.$ As that polynomial has no more than $n$ roots, it follows that $operatornameImg$ consists of the roots of $x^n-1$ in $mathbbF_p.$ Therefore $S_k=ncdotsumlimits_r^n-1=0r,$ 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 $mathbbF_p,$ i.e. $pmid S_k.$

$square$

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

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

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

Else

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

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

$$impliessum_u=1^p-1u^kequivsum_r=1^p-1(a^r)^kpmod p$$

$$sum_r=1^p-1(a^r)^k=a^kcdotdfrac(a^k)^p-1-1a^k-1$$

Now $(a^k)^p-1=(a^p-1)^kequiv1^kequiv?$

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