applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA

Fermat's Little Theorem

Pierre de Fermat is best known to the general public for what is called his Last Theorem which was really
an unproved conjecture. Most likely he did not have α proof for his Last Theorem. However he may well have had α proof
for what came to be called his Little Theorem even though he did not communicate it.

If p is α prime number and α is an integer such that the greatest common divisor of α and p is unity
then:

Consider the remainders of the set of numbers {α, 2α, 3α, …, (p-1)α} upon division by p.
These remainders have to all be distinct and different from 0. If the remainder were 0 for some k it would mean that
p divides α contrary to the hypothesis because p does not divide any integer in the set {1, 2, 3, … (p-1)}.

Suppose gα≡hα (mod p) for some g and h in the set {1, 2, 3, … (p-1)}. If gα≡hα (mod p) then ga−ha=kp for some k. This is equivalent to
(g−h)α=kp. Without any loss of generality
it can be assumed that g≥h. Since p does not divide α it must divide (g−h). The only integer in the possible
range
of (g−h) which p divides is 0. Thus g−h=0 and hence g=h.

The remainders of {α, 2α, 3α, …, (p-1)α } upon division by p are just some permutation of {1, 2, 3, … (p-1)}.

Therefore the product of the remainders of the elements of {α, 2α, 3α, …, (p-1)α } is equal to the
product of the elements of the set {1, 2, 3, … (p-1)}. This means

α^{p-1}(p-1)! ≡ (p-1)! (mod p)

But if α^{p-1}(p-1)! ≡ (p-1)! (mod p) then p divides [α^{p-1}(p-1)! − (p-1)!] which is
equivalent to p dividing (α^{p-1}−1)(p-1)!. Since p divides none of the factors of (p-1)! it must
divide (α^{p-1}−1), which is equivalent to

α^{p-1}≡1 (mod p)

If p divides (α^{p-1}−1) it also divides a(α^{p-1}−1), which is equivalent to
(α^{p}−α) and thus

α^{p}≡a (mod p)

Illustration of the Theorem

Consider p=7 and α=4. Four to the sixth power is 4096. This number divided by 7 is 585 with a remainder
of 1. Four to the seventh power is 16384, which has a remainder of 4 upon division by 7.