# Proof of $p \mid m^p-m$ for prime $p$

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.

-
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
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
@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