# inductive proof of Fermat’s little theorem proof

We will show

$${a}^{p}\equiv a\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$$ |

with $p$ prime. The equivalent^{} statement

$${a}^{p-1}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(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\phantom{\rule{veryverythickmathspace}{0ex}}(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\phantom{\rule{veryverythickmathspace}{0ex}}(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)\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$$ |

Therefore by induction^{} it follows that

$${a}^{p}\equiv a\phantom{\rule{veryverythickmathspace}{0ex}}(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 |