Proofs of Fermat's little theorem Proofs of Fermat's little theorem Napalm Death Category="Modular arithmetic"Category="Number theory"Category="Proofs"This article collects together a variety of proofs of Fermat's little theorem, which states that
a p ≡ a (mod p) !
for every Prime number p and every Integer a (see Modular arithmetic).

Simplifications

Some of the proofs of Fermat's little theorem given below depend on two simplifications.

The first is that we may assume that a is in the range 0 ≤ a ≤ p − 1. This is a simple consequence of the laws of Modular arithmetic; we are simply saying that we may first reduce a modulo p.

Secondly, it suffices to prove that

a p - 1 ≡ 1 (mod p)  (X)
for a in the range 1 ≤ a ≤ p − 1. Indeed, if (X) holds for such a, then we can simply multiply both sides by a to obtain the original form of the theorem,
a p ≡ a (mod p) , !
and if a happens to be zero, the original equation in its original form is obviously true anyway.

Proof by counting bracelets

This is perhaps the simplest known proof, requiring the least mathematical background. It is an attractive example of a Combinatorial proof (a proof that involves counting a collection of objects in two different ways).

To keep things simple, let us assume that a is a positive integer. Consider all the possible strings of p symbols, using an Alphabet with a different symbols. The total number of such strings is a p, since there are a possibilities for each of p positions (see Rule of product).

For example, if p = 5 and a = 2, then we can use an alphabet with two symbols (say A and B), and there are 25 = 32 strings of length five:

AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
ABAAA, ABAAB, ABABA, ABABB, ABBAA, ABBAB, ABBBA, ABBBB,
BAAAA, BAAAB, BAABA, BAABB, BABAA, BABAB, BABBA, BABBB,
BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB.

We will argue below that if we remove the strings consisting of a single symbol from the list (in our example, AAAAA and BBBBB), the remaining a p − a strings can be arranged into groups, each group containing exactly p strings. It follows that a p − a is divisible by p.

Bracelets

[image] [image]

Let us think of each such string as representing a bracelet. That is, we connect the two ends of the string together, and regard two strings as the same bracelet if we can rotate one string to obtain the second string; in this case we will say that the two strings are friends. In our example, the following strings are all friends:

AAAAB, AAABA, AABAA, ABAAA, BAAAA.
Similarly, each line of the following list corresponds to a single bracelet.
AAABB, AABBA, ABBAA, BBAAA, BAAAB,
AABAB, ABABA, BABAA, ABAAB, BAABA,
AABBB, ABBBA, BBBAA, BBAAB, BAABB,
ABABB, BABBA, ABBAB, BBABA, BABAB,
ABBBB, BBBBA, BBBAB, BBABB, BABBB,
AAAAA,
BBBBB.
Notice that in the above list, some bracelets are represented by five different strings, and some only by a single string, so the list shows very clearly why 32 − 2 is divisible by 5.

One can use the following rule to work out how many friends a given string S has:

If S is built up of several copies of the string T, and T cannot itself be broken down further into repeating strings, then the number of friends of S (including S itself) is equal to the length of T.

For example, suppose we start with the string S = "ABBABBABBABB", which is built up of several copies of the shorter string T = "ABB". If we rotate it one symbol at at time, we obtain the following three strings:

ABBABBABBABB,
BBABBABBABBA,
BABBABBABBAB.
There aren't any others, because ABB is exactly three symbols long, and cannot be broken down into further repeating strings.

Completing the proof

Using the above rule, we can complete the proof of Fermat's little theorem quite easily, as follows. Our starting pool of a p strings may be split into two categories:

The second category contains a p − a strings, and they may be arranged into groups of p strings, one group for each bracelet. Therefore a p − a must be divisible by p, as promised.

Proof using modular arithmetic

This proof requires some background in Modular arithmetic.

Let us assume that a is positive and not divisible by p.

The idea is that if we write down the sequence of numbers

a, 2a, 3a, …, (p-1)a  (A)
and reduce each one modulo p, the resulting sequence turns out to be a rearrangement of
1, 2, 3, …, p-1.   (B)
Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo p:
a × 2a × 3a × … × (p-1)a ≡ 1 × 2 × 3 × … (p-1) (mod p) .
Collecting together the a terms yields
a p - 1 (1 × 2 × 3 × … × (p-1)) ≡ 1 × 2 × 3 × … (p-1) (mod p) .
Finally, we may "cancel out" the numbers 1, 2, ..., p − 1 from both sides of this equation, obtaining
a p - 1 ≡ 1 (mod p) . !

There are two steps in the above proof that we need to justify:

We will prove these things below; let us first see an example of this proof in action.

An example

If a = 3 and p = 7, then the sequence in question is
3, 6, 9, 12, 15, 18; !
reducing modulo 7 gives
3, 6, 2, 5, 1, 4, !
which is just a rearrangement of
1, 2, 3, 4, 5, 6. !
Multiplying them together gives
3 × 6 × 9 × 12 × 15 × 18 ≡ 3 × 6 × 2 × 5 × 1 × 4 ≡ 1 × 2 × 3 × 4 × 5 × 6 (mod 7) ; !
that is,
3 6 (1 × 2 × 3 × 4 × 5 × 6) ≡ (1 × 2 × 3 × 4 × 5 × 6) (mod 7) . !
Cancelling out by 1, 2, ... up to 6 yields
3 6 ≡ 1 (mod 7) , !
which is Fermat's little theorem for the case a = 3 and p = 7.

The cancellation law

Let us first explain why it is valid, in certain situations, to "cancel". The exact statement is as follows. If u, x and y are integers, and u is not divisible by p, and if
ux ≡ uy (mod p) , !
then we may "cancel" u to obtain
x ≡ y (mod p) . !
Our use of this cancellation law in the above proof of Fermat's little theorem was valid, because the numbers 1, 2, ..., p − 1 are certainly not divisible by p (indeed they are smaller than p).

We can prove the cancellation law easily using Euclid's lemma, which states that if a prime p divides a product rs (where r and s are integers), then either p divides r or p divides s. Indeed, the equation

ux ≡ uy (mod p) , !
simply means that p divides ux − uy = u(x − y). Since we are assuming that p does not divide u, Euclid's lemma tells us that it must divide x − y instead; that is,
x ≡ y (mod p) . !

(Note that the conditions under which the cancellation law holds are quite strict, and this explains why Fermat's little theorem demands that p be a prime. For example, 2 × 2 ≡ 2 × 5 (mod 6), but we cannot conclude that 2 ≡ 5 (mod 6), since 6 is not prime.)

The rearrangement property

Finally, we must explain why the sequence
a, 2a, 3a, …, (p-1)a, !
when reduced modulo p, becomes a rearrangement of the sequence
1, 2, 3, …, p-1. !
To start with, none of the terms a, 2a, ..., (p − 1)a can be equal to zero modulo p, since if k is one of the numbers 1, 2, ..., p − 1, then k is not divisible by p, and neither is a, so Euclid's lemma tells us that ka cannot be divisible by p. Therefore, at least we know that the numbers a, 2a, ..., (p − 1)a, when reduced modulo p, must be found among the numbers 1, 2, 3, ..., p − 1.

Furthermore, the numbers a, 2a, ..., (p − 1)a must all be distinct after reducing them modulo p, because if

ka ≡ ma (mod p) , !
where k and m are one of 1, 2, ..., p − 1, then the cancellation law tells us that
k ≡ m (mod p) . !

To summarise: when we reduce the p − 1 numbers a, 2a, ..., (p − 1)a modulo p, we obtain distinct members of the sequence 1, 2, ..., p − 1. Since there are exactly p − 1 of these, the only possibility is that the former are a rearrangement of the latter.

Proof using group theory

This proof requires the most basic elements of Group theory.

The idea is to recognise that the set G = {1, 2, ..., p − 1}, with the operation of multiplication (taken modulo p), forms a group. The only group axiom that requires some effort to verify is that each element of G is invertible. Taking this on trust for the moment, let us assume that a is in the range 1 ≤ a ≤ p − 1, that is, a is an element of G. Let k be the order of a, so that

a k ≡ 1 (mod p) . !
By Lagrange's theorem, k divides the order of G, which is p − 1, so p − 1 = km for some positive integer m. Then
a p - 1 ≡ a km ≡ (a k ) m ≡ 1 m ≡ 1 (mod p) . !

The invertibility property

To prove that every element b of G is invertible, we may proceed as follows. First, b is not divisible by p (since it is simply too small), so it is relatively prime to p. Then Bézout's identity assures us that there are integers x and y such that
bx + py = 1. !
Reading this equation modulo p, we see that x is an inverse for b, since
bx ≡ 1 (mod p) . !
Therefore every element of G is invertible, so as remarked earlier, G is a group.

For example, when p = 11, the inverses of each element are given as follows:

{| border="1" cellspacing="0" cellpadding="8"
| align=center | a | 1