# inductive proof of Fermat’s little theorem proof

We will show

 $a^{p}\equiv a\pmod{p}$

with $p$ prime. The equivalent statement

 $a^{p-1}\equiv 1\pmod{p}$

when $p$ does not divide $a$ follows by cancelling $a$ both sides (which can be done since then $a,p$ are coprime).

When $a=1$, we have

 $1^{p}\equiv 1\pmod{p}$

Now assume the theorem holds for some positive $a$ and we want to prove the statement for $a+1$. We will have as a direct consequence that

 $a^{p}\equiv a\pmod{p}$

Let’s examine $a+1$. By the binomial theorem, we have

 $\displaystyle(a+1)^{p}$ $\displaystyle\equiv$ $\displaystyle{{p}\choose{0}}a^{p}+{{p}\choose{1}}a^{p-1}+\cdots+{{p}\choose{p-% 1}}a+1$ $\displaystyle\equiv$ $\displaystyle a+pa^{p-1}+p\frac{(p-1)}{2}a^{p-2}+\cdots+pa+1$ $\displaystyle\equiv$ $\displaystyle(a+1)+[pa^{p-1}+p\frac{(p-1)}{2}a^{p-2}+\cdots+pa]$

However, note that the entire bracketed term is divisible by $p$, since each element of it is divsible by $p$. Hence

 $(a+1)^{p}\equiv(a+1)\pmod{p}$

Therefore by induction it follows that

 $a^{p}\equiv a\pmod{p}$

for all positive integers $a$.

It is easy to show that it also holds for $-a$ whenever it holds for $a$, so the statement works for all integers $a$.

Title inductive proof of Fermat’s little theorem proof InductiveProofOfFermatsLittleTheoremProof 2013-03-22 11:47:46 2013-03-22 11:47:46 mathcam (2727) mathcam (2727) 17 mathcam (2727) Proof msc 11A07 FermatsTheoremProof