San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
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.

## Proof:

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.

NOte that

#### (α) (2α) (3α) ·…·((p-1)α) = αp-1(1·2·3·…·(p-1))

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

## 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.