Proofs of Fermat's little theorem

This is a collection of proofs of Fermat's little theorem:

a^p = a (mod p)

for every prime number p and every integer a.

Note that it is enough to prove

a^p-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)) * a^p-1 = 1*2*3*...(p-1) (mod p)

Now we would like to cancel the common term (p-1)! 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:

a^p-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 = a^p + b^p mod p

when p is prime. The Binomial theorem tells us that

<math> (a+b)^{p} = \sum_{i=0}^{p} {p \choose i} a^{i} b^{p-i} = a^{p} + b^{p} + \sum_{i=1}^{p-1} {p \choose i} a^{i} b^{p-i} </math>

<math> ({}_{i}^{p}) </math> is, by the fundamental theorem of arithmetic, a multiple of p, so the whole term <math> ({}_{i}^{p}) a^{i} b^{p-i} </math> 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 a^p + b^p 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, a^p mod p = a.
2. We assume for now that when a = k, the theorem is true, that is, we assume that k^p mod p = k, and see what happens when a = k + 1:

(k + 1)^p mod p

= k^p + 1^p mod p (by the statement shown above)

= k^p + 1 mod p.

Since we assumed that k^p 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:

• AAAA... and BBBB... and all a unicolor bracelets are special cases; these bracelets can be made out of only one (kind of) open chain.

• Anything else can be made out of p different open chains. Proof: Take such a bracelet and open it as many ways as you can. Each way will be different, because of this (next argument is actually incomplete but hints at the general idea):
  • Let us say it is a 7-link chain. Open it up and label the links abcdefg. Now if you opened it up in a different way, say between a and b, you would get the open chain bcdefga, and if the two were equal, we'd have a=b=c=d=e=f=g, which leads us to a unicolor bracelet, which was excluded. If instead you cut between c and d, we'd get a=c=e=g=b=d=f, which again leads to a unicolor bracelet. The only way it can come out even at any time is if we can find a number less than p that is coprime to p, but since p is prime, we can't!

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

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 x_n+1 = f(x_n),    n = 0, 1, 2, ... If x₀ is chosen in the interval [-1,1], then all x_n 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 f^p has 2^p fixed points which are solutions of:

x = 1 ± 2 ± 4 ± ... ± 2^p 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 2^p – 2 fixed points, forming disjoint orbits of period p. Then (2^p – 2)/p is a natural number, the number of orbits of period p. So p' divides 2p - 2. QED

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, <math> a^{q} = 1 \mod p </math>. But since p-1 = rq for some integer r, <math>a^{p-1} = 1 \mod p</math>. Add the special case where a = p and we get the full proof.