# Deriving Fermat's little theorem from $(a+1)^p\equiv a^p+1$ modulo $p$?

It is known that $p$ divides the binomial coefficient $\binom{p}{i}$ for $1\leq i\leq p-1$. So from the binomial theorem, it is not hard to see $(a+1)^p\equiv a^p+1$ modulo $p$.

Is there a way to derive Fermat's little theorem $a^p\equiv a$ mod $p$, without appealing to Lagrange's theorem? I feel like I could say $(\mathbb{Z}/p\mathbb{Z})^\times$ is a cyclic group of order $p-1$, thus $(a+1)^p\equiv a+1$, hence $a+1\equiv a^p+1$, but this seems to miss this point since I would know $a^p\equiv a$ from the get go.

-
@ErickWong: I misunderstood the problem. Sorry. :( –  Babak S. Dec 28 '12 at 18:29

We will prove by induction that for all $n\in N$ we have $n^p=n\pmod p$. The base ($n=0$) is easy to verify.

Induction step:

$$(n+1)^p\equiv n^p+1\equiv n+1 \pmod p$$

(By the induction hypothesis, $n^p\equiv n \pmod p$

-
Don't you think we need group theory tag for question, cause the OP is willing to use that tool. –  Babak S. Dec 28 '12 at 11:52
I thought that the OP wanted a proof that does not use group theory –  Amr Dec 28 '12 at 12:02
+1: Amr I took the liberty of TeXifying the congruences. I think the spacing of parentheses looks nicer this way. If you disagree, then I apologize, and change it back. –  Jyrki Lahtonen Dec 28 '12 at 12:06
@JyrkiLahtonen , Thank you they are better now. –  Amr Dec 28 '12 at 12:13
+1 Very nice as it uses directly and in a simple way what the OP assumes: $$\forall 0<k<p\;\;,\;\;p\mid\binom{p}{k}$$ –  DonAntonio Dec 28 '12 at 13:02