Main Page | See live article | Alphabetical index

Proofs of Fermat's little theorem

This is a collection of proofs of Fermat's little theorem:
ap = a (mod p)
for every prime number p and every integer a.

Note that it is enough to prove

ap-1 = 1 (mod p)
for every integer a which is relatively prime to p (i.e. not a multiple of p). Multiplying with a then gives the above version of the theorem for those numbers a; for the multiples of p the above version is clear anyway.

Table of contents
1 A direct proof
2 Inductive proof with the binomial theorem
3 A proof using bracelets
4 A proof using dynamical systems
5 A second proof using Dynamical systems
6 A proof using group theory

A direct proof

We will assume a to be relatively prime to p. This proof will make use of our base a multiplied by all the numbers from 1 to p-1. It turns out that if p is prime, the values 1a through (p-1)a (modulo p) are just the numbers from 1 through p-1 rearranged, a consequence of the following lemma. We then multiply all those numbers together, resulting in a formula from which the theorem follows.

Lemma: If a is relatively prime to p and x and y are integers such that xa = ya (mod p), then x = y (mod p).

Proof of lemma: xa = ya (mod p) means that p divides xa - ya = a (x - y). We know that a does not contain the prime factor p, so (x - y) must contain it, since the prime factorization is unique by the fundamental theorem of arithmetic. So p divides (x - y), which means x = y (mod p), which completes the proof of the lemma.

Proof of theorem: Consider the set P = {1a, 2a, 3a, ... (p-1)a}. These numbers are different modulo p by the lemma, and none of them is zero modulo p (again by the lemma: 0a = ka (mod p) would imply 0 = k modulo p, but k is too small for that). So modulo p, the set P is the same as the set N = {1, 2, 3, ... (p-1)}. So if we multiply the elements of these two sets together, we will get the same result modulo p:

1a * 2a * 3a * ... (p-1)a = 1 * 2 * 3 * ... (p-1) (mod p)

Regrouping the left side:

(1*2*3*...(p-1)) * ap-1 = 1*2*3*...(p-1) (mod p)

Now we would like to cancel the common term (p-1)factorial from both sides. This is allowed by the lemma, since p and (p-1)! can have no factor in common, again by the fundamental theorem of arithmetic. Dividing out (p-1)!, we get:

ap-1 = 1 (mod p).

Q.E.D

Inductive proof with the binomial theorem

Here we use mathematical induction. First, the theorem is true for a=1, then one proves that that if it is true for a = k, it is also true for a = k + 1, concluding that the theorem is true for all a.

Before the main argument the following lemma is needed

(a + b)p mod p = ap + bp mod p
when p is prime. The Binomial theorem tells us that

is, by the fundamental theorem of arithmetic, a multiple of p, so the whole term   is a multiple of p if 0 < i < p. This means the whole sum from i = 1 to i = p'\' - 1 equals 0 mod p. So, (a + b)p mod p indeed equals ap + bp mod p when p'' is prime.

Back to the proof of the theorem. We proceed now with the two induction steps.
  1. Obviously, when a = 1, ap mod p = a.
  2. We assume for now that when a = k, the theorem is true, that is, we assume that kp mod p = k, and see what happens when a = k + 1:
(k + 1)p mod p
= kp + 1p mod p (by the statement shown above)
= kp + 1 mod p.
Since we assumed that kp mod p = k, we conclude that (k + 1)p mod p = k + 1, which is what we wanted to demonstrate.

A proof using bracelets

Here is an interesting proof which involves very little symbolic mumbo-jumbo.

Let us say that I make closed bracelets out of open chains that consist of p coloured links, with a choice of a different colours; and that I can use the links in any combination. Now, since these are closed bracelets, if I give you one, but you will be able to rotate it at will. So the 9-link bicolor bracelet ABAABBBBB is the same as BBABAABBB (you can rotate the bracelet), but it is different from BBBBBAABA (you cannot reverse it or recolour it).

Some 9-link bracelets can be made from only one "directional" open chain, such as AAAAAAAAA; however, some can be made from more than one such chain (ABBABBABB, BABBABBAB, BBABBABBA all make the same bracelet).

If you tell me how many links a bracelet is to have (call this number p), how many different bracelets of that size can I make, and out of how many distinct open chains can I make each one? Since it is Fermat's Little Theorem we are trying to prove, let us restrict ourselves to cases where p is prime. Let us find the answer thus:

So what do we have? We have a unicolor bracelets, each from one unicolor open chain; and the other ap-a (multicolor) open chains make (ap-a)/p bracelets, each from p open chains. This shows that p divides (ap-a).

A proof using dynamical systems

Here we prove the special case a = 2 using the fixed points of a 1D-map which is commonly encountered in dynamical systems.

Define the "tent" map:

f(x) = 1 - 2 |x| for x in the interval [-1, 1]
and consider the dynamical system xn+1 = f(xn),    n = 0, 1, 2, ... If x0 is chosen in the interval [-1,1], then all xn will remain in that same interval.

The fixed points of f are -1 and 1/3.

If p is a prime number, then the p-iterated map fp has 2p fixed points which are solutions of:

x = 1 ± 2 ± 4 ± ... ± 2p x

But two of these fixed points are –1 and 1/3. All the others must have period p, since any period would have to be divisor of p but the prime number p doesn't have any non-trivial divisors.

So, we have 2p – 2 fixed points, forming disjoint orbits of period p. Then (2p – 2)/p is a natural number, the number of orbits of period p. So p' divides 2p'' - 2.

Take this into account: numerical calculations must fail for great p due to rounding errors of the calculator or the computer.

A second proof using Dynamical systems

The following needs to be checked and cleaned up.

For any n we define in the interval (0,1) ->(0,1) ( ) closed

Tn(x) = FP(nx), x<1

Tn(x) = 1, x=1

FP: Fractional Part

Lemma 1: Let n be an integer greater than 1. The function Tn(x) has n fixed points in (0,1).

Lemma 2: Let a and b be positive integers. Then for all x belognig to (0,1):

Ta(Tb(x)) = Tab(x)

Using values a and p, we consider the p-periodic point of Ta. These p-periodic points are fixed points of Ta iterated p times, which is Ta^p. This has a^p fixed points. Of these, exactly a are fixed points of Ta.

Since p is prime the rest of them have minimal period p under Ta. This means that there are a^p-a points that have minimal period p. Since each point with minimal period p lies in an orbit p, there are (a^p-a)/p orbits of size p. Since this is an integer, we see that p divides (a^p-a).

A proof using group theory

This is similar to the direct proof. Trivially, the integers 1, ..., p-1 form a group under multiplication mod p. This group is finite, so clearly the subgroup generated by any a in 1, ..., p-1 must have size q where q divides the size of the original group, p-1. That is, . But since p-1 = rq for some integer r, . Add the special case where a = p and we get the full proof.