# 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. :( – mrs Dec 28 '12 at 18:29

## 1 Answer

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. – mrs 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