# Prove congruence using Fermat's Little Theorem

I'm trying to prove that if $(p - 1)\mathrel{\mid} n$ where $p$ is prime and $n ≥ 1$, then

$$1^n + 2^n + \dotsb + (p - 1)^n + p^n ≡ -1 \pmod p.$$

My attempt thus far:

If $(p - 1)\mathrel{\mid} n$ then $n = (p - 1)d$ for some $d ≥ 0$, so we can substitute and obtain

$$1^n + 2^n + \dotsb + (p - 1)^n + p^n ≡ 1^{(p - 1)d} + 2^{(p - 1)d} + \dotsb + (p - 1)^{(p - 1)d} + p^{(p - 1)d}.$$

Note $p$ cannot divide $p - 1$, nor can $p$ divide any value less than $p$ (i.e. cannot divide $1, 2, \dotsc, p - 2$). Using Fermat's little theorem and simplifying (mod $p$) this congruence becomes

$$1^d + 2^d + ... + (p - 1)^d + 0.$$

And from here I'm lost. I'm not even sure if I'm on the right track here. I'd appreciate any help or suggestions.

## 3 Answers

For $1\le a\le p-1$, we have $a^{p-1}\equiv 1\pmod{p}$ by Fermat's Theorem. Then $a^n=(a^{p-1})^d\equiv 1^d\equiv 1\pmod{p}$.

• Thank you for clearing that up. I can't believe I missed it! – Guest Mar 8 '15 at 18:54
• You are welcome. Minor slip, unlikely to happen again. The intuition is that $a^{p-1}$ "is" $1$. – André Nicolas Mar 8 '15 at 18:57

The problem is that you simplified in a wrong way. You have $j^{p-1}$ is $1$ modulo $p$. Not $j$ as you wrote. Thus you get $1^d + 1^d + \dots + 1^d + 0$.

• Clearly I've been overthinking this one. Thank you so much for your comment. – Guest Mar 8 '15 at 18:53

The integers from $0$ to $p-1$ form a field mod p. The nonzero elements of this field are solutions to the equation $x^{p-1}-1=0$, from Fermat. From Vieta, all the elementary polynomials of the roots of order less than $p-1$ are zero, and thus any symmetric polynomial of the roots of order less than $p-1$ is zero.