Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks

Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and $-1\pmod{p}$ if $p-1\mid k$.

My work is leading where I didn't expect to go. Here I assume $p$ id odd. First, if $p-1\mid k$, then we can wrike $k=(p-1)j$ for some $j$. But then $$ 1^k+\cdots+(p-1)^k\equiv 1^{(p-1)j}+\cdots+(p-1)^{(p-1)j}\equiv \underbrace{1+\cdots+1}_{p-1\text{ times}}=\frac{(p-1)p}{2}\equiv 0\pmod{p} $$ since $p-1$ is even.

Secondly, I suppose $p-1\nmid k$. WLOG, I can assume $0<k<p-1$, Since if $k=(p-1)j+r$ with $0<r<p-1$, then $$ a^k\equiv a^{(p-1)j+r}\equiv a^r\pmod{p}. $$

Then if $g$ is a primitive root, $$ 1^k+\cdots+(p-1)^k=\sum_{i=1}^{p-1}(g^k)^i=\frac{g^k(1-g^{k(p-1)})}{1-g^k}. $$ Since $g$ is primitive, $p\nmid 1-g^k$, but $p\mid 1-g^{k(p-1)}$, so the above sum is again congruent to $0\pmod{p}$.

So in all cases, I get the sum is congruent to $0$ regardless. Have I messed up, or is there a typo? Thanks.

share|cite|improve this question
up vote 4 down vote accepted

In the case that $p-1\mid k$, you should have had $$\underbrace{1+\cdots+1}_{p-1\text{ times}}=p-1\equiv -1\bmod p.$$

share|cite|improve this answer
Oh, silly mistake on my part! I had the sum $1+2+\cdots+p-1$ still in my head. – Dedede Jan 2 '13 at 2:18
Don't worry, happens to all of us sometimes :) – Zev Chonoles Jan 2 '13 at 2:18

Let $g$ be a primitive root of $p$. Then $2,3,\dots,p-1$ are congruent, in some order, to $g,g^2, \dots,g^{p-2}$.

Thus our sum $S_k$ is congruent to $$1+g^{k}+g^{2k}+\cdots +g^{(p-2)k}\tag{$1$}$$ modulo $p$.

If $p-1$ divides $k$, then by Fermat's Theorem each term is congruent to $1$ modulo $p$. There are $p-1$ terms, so the sum is congruent to $-1$ modulo $p$.

Now suppose that $p-1$ does not divide $k$. Multiplying expression $(1)$ by $1-g^k$, we obtain $$(1-g^k)S_k\equiv 1-g^{(p-1)k}\equiv 0\pmod{p}.$$ Since $p-1$ does not divide $k$, and $g$ has order $p-1$, it follows that $1-g^k\not\equiv 0\pmod{p}$. It follows that $S_k\equiv 0\pmod{p}$.

share|cite|improve this answer
Thanks! The second half is much slicker than what I did. – Dedede Jan 2 '13 at 2:27
Dear Andre - I would be remiss if I did not thank you for your generosity and most beautiful answers, helping all of us here. Best regards, – TheBirdistheWord Aug 30 '14 at 18:06
Thank you. The above answer is not a good example of beauty, the conceptual content is not high. – André Nicolas Aug 30 '14 at 18:11


If $p-1 \mid k$, then by Fermat Little Theorem $j^k \equiv 1 \pmod p$.

If $p-1 \nmid k$, then pick some $1 < j < p-1$ so that $j^k \ne 1 \pmod p$. Then

$$f(x)= j^kx$$

is a bijection from $\{ 1,2,.., p-1\}$ to $\{ 1,2,.., p-1\}$. This shows that

$$j^k(1^k+2^k+\cdots+(p-1)^k)=1^k+2^k+\cdots+(p-1)^k \pmod p$$

from where your claim follows..

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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