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

## Statement

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

${\displaystyle a^{p-1}\equiv 1\mod {p}}$

## Proofs

There are many proofs of Fermat's Little Theorem.

Proof 1 (Bijection)

Define a function ${\displaystyle f(x)=ax}$  (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, ${\displaystyle f(a^{-1}m)=m}$ . Then ${\displaystyle f}$  is surjective.

In addition, if ${\displaystyle f(x)=f(y)}$ , then ${\displaystyle ax\equiv ay}$  and ${\displaystyle a^{-1}ax\equiv x\equiv y\equiv a^{-1}ay}$ . Then ${\displaystyle f}$  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

${\displaystyle \prod _{k=1}^{p-1}k\equiv \prod _{k=1}^{p-1}ak{\pmod {p}}}$  and that
${\displaystyle \prod _{k=1}^{p-1}k\equiv a^{p-1}\prod _{k=1}^{p-1}k{\pmod {p}}}$ .

Then

${\displaystyle a^{p-1}\equiv 1\mod {p}}$ .