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.

This problem is well-known, but my proof is different from the one I found, so just decided to put it here in case someone finds a mistake.

So I want to prove $p \mid m^p-m$, where $p$ is a prime number and $m \in \mathbb Z$. Obviously $m^p-m=m(m^{p-1}-1)$, and $p-1$ is an even number. Assuming $p \nmid m$, $m$ can be written as $p \pm 1, \pm 2, \ldots ,\pm \frac{p-1}{2},$ and then for $m=p \pm r, \ r \in \mathbb{Z}$, we have $p \mid m^{p-1}-1$.

I prove the conjecture by induction:

  1. $m=p+1$: The expression in the brackets becomes (expanding in Binomial series) $$ (1+p)^{p-1}-1=\sum_{k=0}^{p-1}\binom{p-1}{k}p^k-1=\binom{p-1}{1}p+\binom{p-1}{2}p^2+ \cdots,$$ since $1$ cancels out, and this is a multiple of $p$. If $m=p-1$: Applying the same idea, the expression in the brackets becomes $\sum\limits_{k=0}^{p-1}\binom{p-1}{k}p^k (-1)^{p-1-k}-1$, the first term is $(-1)^{p-1}$, and, since $p-1$ is even, it cancels out with $1$ and the rest is a multiple of $p$.

  2. Assume true for $m=p \pm r, \ r \in \mathbb Z$.

  3. $m=p \pm r \pm 1$: once again, expanding in binomial series, I obtain $$\sum_{k=0}^{p-1}\binom{p-1}{k}(p+r)^k -1 .$$ The $1$'s cancel out and the rest is a multiple of $(p+r)$, which, by Step 2 (assumption), $p \mid (p+r)^{p-1}-1$. Similar case when $p -r \pm 1$, which proves the conjecture.

share|improve this question
    
Maybe it would be more appropriate to ask about a particular step in your argument where you think there could possibly be a mistake, or that you're not able to justify completely. As I see it you're not asking anything, just posting your purported proof for everybody else to read and possibly comment on. –  Adrián Barquero Jul 12 '11 at 3:10
    
My main concern here is with the correct use of inductive proof, but I don't exclude other mistakes. –  sigma.z.1980 Jul 12 '11 at 3:14
3  
There are several proofs at en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem including one using induction and the Binomial Theorem. –  Gerry Myerson Jul 12 '11 at 3:40
1  
@user6312: where does $(m+1)^p$ come from? If $p \nmid m$, then $m$ can be written as $p+r: r \pm 1,2,..$ and the inductive proof follows –  sigma.z.1980 Jul 12 '11 at 3:57
    
It is OK if instead of $m$ you write $p+r$. But the problem remains that you have terms with $(p+r)^k$, where $k$ is between $1$ and $p-2$, and the induction hypothesis says nothing about them. –  André Nicolas Jul 12 '11 at 4:04
show 10 more comments

1 Answer

As mentioned in the comments, many proofs can be found here.

The purpose of this post is so that this question does not remain unanswered.

share|improve this answer
add comment

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.