Famous Theorems of Mathematics/Number Theory/Fermat's Little Theorem

Statement

edit

If p is a rational prime, for all integers a ≠ 0,

 

Proofs

edit

There are many proofs of Fermat's Little Theorem.

Proof 1 (Bijection)

Define a function   (mod p). Let S={1,2,...,p-1} and T=f(S)={a,2a,...,(p-1)a}. We claim that these two sets are identical mod p.

Since all integers not equal to 0 have inverses mod p, for any integer m with 1≤m<p,  . Then   is surjective.

In addition, if  , then   and  . Then   is injective, and is bijective between S and T.

Then, mod p, the product of all of the elements of S will be equal to the product of elements of T, meaning that

  and that
 .

Then

 .