5
$\begingroup$

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.

  • 0
    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.2011-07-12
  • 0
    My main concern here is with the correct use of inductive proof, but I don't exclude other mistakes.2011-07-12
  • 3
    There are several proofs at http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem including one using induction and the Binomial Theorem.2011-07-12
  • 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 follows2011-07-12
  • 0
    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.2011-07-12
  • 0
    I'm probably wrong somewhere, but $(p+r)$ is the second step (assumption) so for $(p+r+1)^k, \ 0 \leq k \leq p-1$, the first term cancels out and the rest are the multiples of $p+r$.2011-07-12
  • 0
    Well, I think you can do this. \begin{align*} (m+1-1)^{p} -m &=(m+1)^{p} -{p \choose 1}(m+1)^{p-1} + {p \choose 2} \cdot (m+1)^{p-2} - \cdots -1 -m \\\ &=(m+1)^{p} -1 -m \ (\text{mod} \ p)\\\ &= m^{p} + { p \choose 1}\cdot m^{p-1} + {p \choose 2} \cdot m^{p-2} + \cdots +1 -1 -m \\\ &=m^{p}-m \ (\text{mod} \ p) \end{align*}2011-07-12
  • 0
    @user6312: OK what if I assume $p|m^{p-1}-1$? Then I prove by induction for $m=p \pm 1, r, r+1$? Besides I still don't quite understand in Chandru's proof what to do with $m^p-m$, unless it's an inductive step. In such case I'd probably do something like $(m+1)^p-(m+1)$...2011-07-13
  • 0
    @user6312: OK now I see the logic in Chandru's and your proofs. I agree it is shorter than mine, but nevertheless, since I express $m=p \pm r$ for some r, each term in Binomial expansion is a multiple of $p$ except that which cancels out with 1.2011-07-13
  • 0
    @sigma.z.1980: Two comments ago: You keep repeating that each *term* in *your* binomial expansion is a multiple of $p$ except $\dots$. It is false. Try numerical examples.2011-07-13
  • 0
    @user6312: yes i did try this, but I still don't see where I made a mistake. Besides, why did you delete some of your comments?2011-07-13
  • 0
    @sigma.z.1980: The system seems to get upset if there are many comments. You should delete lots of yours. Yesterday, I decided that maybe you thought $(p+r)^k$ when expanded is mostly $p$'s (true) and the $r^k$ doesn't matter (false).2011-07-13
  • 0
    @Chandrasekhar: Is this a joke? You told us that $m+1-1=m$... I really saw nothing worth mentioning here.2011-08-20
  • 0
    @sigma.z.1980: From the point of view of me, you could try to read some dissertations by Euler, before finding a *novel* proof of the Fermat's little theorem. Indeed, we may say that your proof is similar to that by Euler; if not so, tell me, and I correct this.2011-08-20
  • 0
    @awllower: is it a good thing? But yes thanks, I will read that2011-09-07

1 Answers 1

3

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.