inductive proof of Fermat’s little theorem proof

We will show

$$a^p\equiv a(modp)$$

with $p$ prime. The equivalent statement

$$a^{p-1}\equiv 1(modp)$$

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(modp)$$

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(modp)$$

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

${(a+1)}^p$ $\equiv$ $\left({\displaystyle \genfrac{}{}{0pt}{}{p}{0}}\right)a^p+\left({\displaystyle \genfrac{}{}{0pt}{}{p}{1}}\right)a^{p-1}+\mathrm{\cdots }+\left({\displaystyle \genfrac{}{}{0pt}{}{p}{p-1}}\right)a+1$

$\equiv$ $a+p{a}^{p-1}+p{\displaystyle \frac{(p-1)}{2}}{a}^{p-2}+\mathrm{\cdots }+pa+1$

$\equiv$ $(a+1)+[p{a}^{p-1}+p{\displaystyle \frac{(p-1)}{2}}{a}^{p-2}+\mathrm{\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)(modp)$$

Therefore by induction it follows that

$$a^p\equiv a(modp)$$

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
Canonical name	InductiveProofOfFermatsLittleTheoremProof
Date of creation	2013-03-22 11:47:46
Last modified on	2013-03-22 11:47:46
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	17
Author	mathcam (2727)
Entry type	Proof
Classification	msc 11A07
Related topic	FermatsTheoremProof