Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Using Fermat's Theorem Prove if $p$ is prime, prove $1^p + 2^p + 3^p +...+(p-1)^p \equiv 0 \bmod{p}$

The two definitions of Fermat's Little Theorem is $a^p \equiv a \bmod{p}$ and $a^{p-1} \equiv 1 \bmod{p}$ but I don't know how to use this solve the problem

share|improve this question

5 Answers 5

Hint: Use Fermat's theorem for each $k$ ($1\le k\le p-1$) and add all them up. Then use Gauss's formula for the sum $1+2+\cdots +(p-1)$.

share|improve this answer

Since $1^p \equiv 1$, and $2^p \equiv 2$, $\ldots$ $(p-1)^p \equiv p-1$, we have that

$$1^p + 2^p + \ldots (p-1)^p \equiv 1 + 2 + \ldots + p-1$$

However, we know this sum: $\sum_{i = 1}^{p-1} i = \frac{p (p-1)}{2}$, which for odd primes would be a multiple of $p$, and we are done by reducing modulo $p$, then we only must check the case for $2$, which doesn't hold, and it's awkward...

share|improve this answer

$1^p + ... + (p-1)^p \equiv 1 + 2 + ... (p-1) \equiv (1 + (p-1)) + (2 + (p-2)) + ... +(\frac{p-1}{2} + \frac{p+1}{2}) \equiv p + ... + p \equiv 0 (\mod p) $

Edit: Assuming p is an odd prime, of course

share|improve this answer
    
I understand the 1+(p-1)+2+(p-2)+.... part but how did you come up with (p-1/2 + p+1/2)? –  Cindy Dec 10 '12 at 4:54
    
Because $p$ is odd, that'll be the last two pairs in the sum. Write out some of these sums for various primes and you'll see where it comes from. –  anonymous Dec 10 '12 at 16:39

Before you wonder if you know how to use Fermat's theorem to solve the problem, first wonder if you are able to use Fermat's theorem at all.

There are a lot of things raised to the $p$-th power, and one form of Fermat's theorem tells you something about things raised to the $p$-th power. So you see what Fermat's theorem tells you about them.

You don't do this because you know it will solve the problem: you do this because maybe it will tell you something useful.

As it turns out, the thing it tells you is that your problem is equivalent to a problem you already know how to solve.

share|improve this answer

There is no need of Fermat's theorem. If $p$ is odd, then $p$ divides $$ k^p +(p-k)^p = (k+p-k)\left(k^{p-1}-\ldots+(p-k)^{p-1}\right)=p A, $$ hence by collecting the terms of your sum in couples (just like Gauss did when he was five years old in order to prove that $1+2+\ldots+n = \frac{(n+1)n}{2}$) you get that the sum is a multiple of $p$.

share|improve this answer

Your Answer

 
discard

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.