Famous Theorems of Mathematics/Number Theory/Fermat's Little Theorem
From Wikibooks, open books for an open world
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,...,p1} and T=f(S)={a,2a,...,(p1)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


 .
