inductive proof of Fermat’s little theorem proof

We will show


with p prime. The equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath statement


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

When a=1, we have


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


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

(a+1)p (p0)ap+(p1)ap-1++(pp-1)a+1

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


Therefore by inductionMathworldPlanetmath it follows that


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