Proofs of Fermat's little theorem

This article collects together a variety of proofs of Fermat's little theorem, which states that

$a^p \equiv a \pmod 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} \equiv 1 \pmod p \quad \quad (X)$

for a in the range 1 ≤ a ≤ p − 1. Indeed, if (X) holds for such a, multiplying both sides by a yields the original form of the theorem,

$a^p \equiv a \pmod p, \,\!$

On the other hand, if a equals zero, the theorem holds trivially.

Proof by counting necklaces

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

The proof given here is an adaptation of Golomb's proof.

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 2⁵ = 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.

Necklaces

Necklace representing seven different strings (ABCBAAC, BCBAACA, CBAACAB, BAACABC, AACABCB, ACABCBA, CABCBAA)

Necklace representing only one string (AAAAAAA)

Let us think of each such string as representing a necklace. That is, we connect the two ends of the string together, and regard two strings as the same necklace 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 necklace.

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 necklaces 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 a 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:

• Some strings contain p identical symbols. There are exactly a of these, one for each symbol in the alphabet. (In our running example, these are the strings AAAAA and BBBBB.)
• The rest of the strings use at least two distinct symbols from the alphabet. If we try to break up such a string S into repeating copies of a string T, we find that because p is prime, the only possibility is that T is already the whole string S. Therefore, the above rule tells us that S has exactly p friends (including S itself).

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

Proofs using modular arithmetic

These proofs require some background in modular arithmetic.

First method

To prove:

$a^{p-1} - 1 \equiv 0\pmod p$

Now

$a^{p-1} - 1 = (a-1)(a^{p-2} + a^{p-3} + \cdots + 1)$

If $(a-1) \equiv 0 \pmod p$, $a \equiv 1 \pmod p$ so a to any power is also congruent to 1 mod p, and the above equation is true for any p.

If $(a-1) \not\equiv 0 \pmod p$ and since a < p, it suffices to prove that,

$(a^{p-2} + a^{p-3} + \cdots + 1) \equiv 0\pmod p$

Or

$\sum_{i=0}^{p-2} a^i \equiv 0 \pmod p$

Since p is a prime number, p − 1 can be factorized. Let p − 1 = mn.

Let $a^0\equiv b_1\pmod p,\ a^1\equiv b_2\pmod p,$ etc.

Then the p − 1 terms of aⁱ(mod p) can be tabulated as elements of an $m\times n$ matrix B:

$\begin{bmatrix} b_1 & b_2 & b_3 & \dots & b_n\\ b_{n+1} & b_{n+2} & b_{n+3} & \dots & b_{2n}\\ \vdots & \vdots & \vdots & & \vdots\\ b_{(m-1)n+1} & b_{(m-1)n+2} & b_{(m-1)n+3} & \dots & b_{mn} \end{bmatrix}$

If : $\sum_{j=1}^{mn} b_j \equiv 0 \pmod p$

Then : $\sum_{i=0}^{p-2} a^i \equiv 0 \pmod p$

Lemma 1

If $\sum_{j=1}^n b_j \equiv 0\pmod p$

Then

$\sum_{i=0}^{p-2} a^i \equiv 0 \pmod p$

Proof of Lemma 1:

If $\sum_{j=1}^n b_j \equiv 0\pmod p$

Then $(a - 1) \sum_{j=1}^n b_j = (a - 1)(1 + a^1 + a^2 + \cdots + a^{n-1}) = a^n - 1 \equiv 0 \pmod p$

That is:

$a^n \equiv 1 \pmod p \equiv b_1$

$a^{n+1} \equiv a \pmod p \equiv b_2$

$a^{n+2} \equiv a^2 \pmod p \equiv b_3$ etc.

Thus the elements of second row of matrix B are identical to those of the first row and hence the third and fourth rows etc. That is,

$\begin{bmatrix} b_1 & b_2 & b_3 & \dots & b_n\\ b_{n+1} & b_{n+2} & b_{n+3} & \dots & b_{2n}\\ \vdots & \vdots & \vdots & & \vdots\\ b_{(m-1)n+1} & b_{(m-1)n+2} & b_{(m-1)n+3} & \dots & b_{mn} \end{bmatrix} \equiv \begin{bmatrix} b_1 & b_2 & b_3 & \dots & b_n\\ b_1 & b_2 & b_3 & \dots & b_n\\ \vdots & \vdots & \vdots & & \vdots\\ b_1 & b_2 & b_3 & \dots & b_n\\ \end{bmatrix}$

Thus

$\sum_{j=1}^{mn} b_j \pmod p$

$\equiv m \times \sum_{j=1}^{n} b_j \pmod p$

$\equiv m \times 0\pmod p$

$\equiv 0\pmod p$

and hence

$\sum_{i=0}^{p-2} a^i \equiv 0 \pmod p$

Lemma 2

If : $\sum_{j=1}^n b_j \not\equiv 0\pmod p$

Then

$\sum_{i=0}^{p-2} a^i \equiv 0 \pmod p$

Proof of Lemma 2:

If : $\sum_{j=1}^n b_j \not\equiv 0\pmod p$

From Lemma 1,

$a^n \not\equiv 1\pmod p.$

Thus the elements of second row of matrix B are not identical to that of the first row, neither are the third and fourth rows, etc. Conditions for Lemma 2 shall hold for all factor n | (p − 1), any violation will result in satisfying the condition of Lemma 1 whereby the result has been proven. Consequently each value of b_j must be unique for $j = 1, 2, \dots , mn$.

Since b_j < p, the elements of matrix B are no other than the set of numbers: $\{1, 2, 3, \dots, p-1\}$

Thus

$\sum_{j=1}^{p-1} b_j = \sum_{j=1}^{p-1} j = \frac{p(p-1)}{2}$

Hence

$\sum b_j = \frac{p(p-1)}{2} \equiv 0 \pmod{p}$

We have proven both lemmas and have completed the proof.

Corollary

The proof also leads to the following corollary:

If p is a prime number, there exists an integer n for every integer a such that,

$a^{n} \equiv 1 \pmod{p}$

The integer n is a divisor of (p − 1). The smallest possible integer n is the Carmichael function, λ(p), which is ≤ (p − 1).

Second method

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, \ldots, (p-1)a \quad\quad (A)$

and reduce each one modulo p, the resulting sequence turns out to be a rearrangement of

$1, 2, 3, \ldots, p-1. \quad\quad\quad (B)$

Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo p:

$a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots \times (p-1) \pmod p.$

Collecting together the a terms yields

$a^{p-1} (p-1)! \equiv (p-1)! \pmod p.$

Finally, we may "cancel out" the numbers 1, 2, ..., p − 1 from both sides of this equation, obtaining

$a^{p-1} \equiv 1 \pmod p.\,\!$

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

• Why (A) is a rearrangement of (B), and
• Why it is valid to "cancel" in the setting of modular arithmetic.

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 \times 6 \times 9 \times 12 \times 15 \times 18 \equiv 3 \times 6 \times 2 \times 5 \times 1 \times 4 \equiv 1 \times 2 \times 3 \times 4 \times 5 \times 6 \pmod 7;\,\!$

that is,

$3^6 (1 \times 2 \times 3 \times 4 \times 5 \times 6) \equiv (1 \times 2 \times 3 \times 4 \times 5 \times 6) \pmod 7.\,\!$

Canceling out 1 × 2 × 3 × 4 × 5 × 6 yields

$3^6 \equiv 1 \pmod 7, \,\!$

which is Fermat's little theorem for the case a = 3 and p = 7.

The rearrangement property

Finally, we must explain why the sequence

$a, 2a, 3a, \ldots, (p-1)a, \,\!$

when reduced modulo p, becomes a rearrangement of the sequence

$1, 2, 3, \ldots, p-1.\,\!$

To start with, none of the terms a, 2a, ..., (p − 1)a can be congruent to zero modulo p, since if k is one of the numbers 1, 2, ..., p − 1, then k is relatively prime with p, and so is a, so Euclid's lemma tells us that ka shares no factor with 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. (also simply by the pigeonhole principle).

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

$ka \equiv ma \pmod p, \,\!$

where k and m are one of 1, 2, ..., p − 1, then the cancellation law tells us that

$k \equiv m \pmod 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.

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 \equiv uy \pmod p, \,\!$

then we may "cancel" u to obtain

$x \equiv y \pmod 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 generally states that if an integer b divides a product rs (where r and s are integers), and b is relatively prime to r, then b must divide s. Indeed, the equation

$ux \equiv uy \pmod p, \,\!$

simply means that p divides ux − uy = u(x − y). Since p cannot divide u, since each factor of u is less than p and p is prime, therefore it cannot be the product of any factors of u, Euclid's lemma tells us that it must divide x − y instead; that is,

$x \equiv y \pmod 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 in order to make a general case for all n. For example, 2 × 2 ≡ 2 × 5 (mod 6), but we cannot conclude that 2 ≡ 5 (mod 6), since 6 is not prime. See below for a more extensive proof for all p)

Applications to Euler's theorem

This method can also be used to prove Euler's theorem, with a slight alteration in that 1 to (p-1) is substituted for the numbers less than and relatively prime to some base m (instead of p). Both the rearrangement property and the cancellation law are still satisfied and can be utilized.

For example:

$a \times 3a \times 7a \times 9a \equiv 1 \times 3 \times 7 \times 9 \pmod {10}. \,\!$

Therefore,

${a^{\varphi(10)}} \equiv 1 \pmod {10}. \,\!$

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 \equiv 1 \pmod 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} \equiv a^{km} \equiv (a^k)^m \equiv 1^m \equiv 1 \pmod p. \,\!$

The invertibility property

To prove that every element b of G is invertible, we may proceed as follows. First, b 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 \equiv 1 \pmod 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:

a	1	2	3	4	5	6	7	8	9	10
a −1	1	6	4	3	9	2	8	7	5	10

Proof using the binomial theorem

This proof uses induction to prove the theorem for all integers a ≥ 0.

The base step, that 0 ^p ≡ 0 (mod p), is true for modular arithmetic because it is true for integers. Next, we must show that if the theorem is true for a = k, then it is also true for a = k+1. For this inductive step, we need the following lemma.

Lemma. For any prime p,

$(x+y)^p \equiv x^p+y^p \pmod{p}.\,$

An alternative way of viewing this lemma is that it states that

$(x+y)^p = x^p + y^p\,\!$

for any x and y in the finite field GF(p).

Postponing the proof of the lemma for now, we proceed with the induction.

Proof. Assume k^p ≡ k (mod p), and consider (k+1)^p. By the lemma we have

$(k+1)^p \equiv k^p + 1^p \pmod{p}.\,$

Using the induction hypothesis, we have that k^p ≡ k (mod p); and, trivially, 1^p = 1. Thus

$(k+1)^p \equiv k + 1 \pmod{p},\,$

which is the statement of the theorem for a = k+1. ∎

In order to prove the lemma, we must introduce the binomial theorem, which states that for any positive integer n,

$(x+y)^n=\sum_{i=0}^n{n \choose i}x^{n-i}y^i,$

where the coefficients are the binomial coefficients,

${n \choose i}=\frac{n!}{i!(n-i)!},$

described in terms of the factorial function, n! = 1×2×3×⋯×n.

Proof of lemma. The binomial coefficients are all integers and when 0 < i < p, neither of the terms in the denominator includes a factor of p, leaving the coefficient itself to possess a prime factor of p which must exist in the numerator, implying that

${p \choose i} \equiv 0 \pmod{p},\qquad 0 < i < p.$

Modulo p, this eliminates all but the first and last terms of the sum on the left-hand side of the binomial theorem for prime p. ∎

The primality of p is essential to the lemma; otherwise, we have examples like

${4 \choose 2} = 6,$

which is not divisible by 4.

Proof using dynamical systems

This proof uses some basic concepts from dynamical systems.

We start by considering a family of functions, T_n(x), where n ≥ 2 is an integer, mapping the interval [0, 1] to itself by the formula

$T_n(x) = \begin{cases} \{ nx \} & 0 \leq x < 1, \\ 1 & x = 1,\end{cases}$

where {y} denotes the fractional part of y. For example, the function T₃(x) is illustrated below:

A number x₀ is said to be a fixed point of a function f(x) if f(x₀) = x₀; in other words, if f leaves x₀ fixed. The fixed points of a function can be easily found graphically: they are simply the x-coordinates of the points where the graph of f(x) intersects the graph of the line y = x. For example, the fixed points of the function T₃(x) are 0, 1/2, and 1; they are marked by black circles on the following diagram.

We will require the following two lemmas.

Lemma 1. For any n ≥ 2, the function T_n(x) has exactly n fixed points.

Proof. There are three fixed points in the illustration above, and the same sort geometrical argument applies for any n ≥ 2.

Lemma 2. For any positive integers n and m, and any 0 ≤ x ≤ 1,

$T_m(T_n(x)) = T_{mn}(x).\,$

In other words, T_mn(x) is the composition of T_n(x) and T_m(x).

Proof. The proof of this lemma is not difficult, but we need to be slightly careful with the endpoint x = 1. For this point the lemma is clearly true since

$T_m(T_n(1)) = T_m(1) = 1 = T_{mn}(1).\,\!$

So let us assume that 0 ≤ x < 1. In this case,

$T_n(x) = \{nx\} < 1, \,\!$

so T_m(T_n(x)) is given by

$T_m(T_n(x)) = \{m\{nx\}\}.\,\!$

Therefore, what we really need to show is that

$\{m\{nx\}\} = \{mnx\}.\,\!$

To do this we observe that {nx} = nx − k, where k is the integer part of nx; then

$\{m\{nx\}\} = \{mnx - mk\} = \{mnx\} \,\!$

since mk is an integer.

Now let us properly begin the proof of Fermat's little theorem, by studying the function T_{a ^p}(x). We will assume that a is positive. From Lemma 1, we know that it has a ^p fixed points. By Lemma 2 we know that

$\begin{matrix} T_{a^p}(x) = & \underbrace{T_a(T_a( \cdots T_a(x) \cdots ))}, \\ & p \, \textrm{ times} \\ \end{matrix}$

so any fixed point of T_a(x) is automatically a fixed point of T_{a ^p}(x).

We are interested in the fixed points of T_{a ^p}(x) that are not fixed points of T_a(x). Let us call the set of such points S. There are a ^p − a points in S, because by Lemma 1 again, T_a(x) has exactly a fixed points. The following diagram illustrates the situation for a = 3 and p = 2. The black circles are the points of S, of which there are 3² − 3 = 6.

The main idea of the proof is now to split the set S up into its orbits under T_a. What this means is that we pick a point x₀ in S, and repeatedly apply T_a(x) to it, to obtain the sequence of points

$x_0, T_a(x_0), T_a(T_a(x_0)), T_a(T_a(T_a(x_0))), \ldots. \,\!$

This sequence is called the orbit of x₀ under T_a. By Lemma 2, this sequence can be rewritten as

$x_0, T_a(x_0), T_{a^2}(x_0), T_{a^3}(x_0), \ldots.$

Since we are assuming that x₀ is a fixed point of T_{a ^p}(x), after p steps we hit T_{a ^p}(x₀) = x₀, and from that point onwards the sequence repeats itself.

However, the sequence cannot begin repeating itself any earlier than that. If it did, the length of the repeating section would have to be a divisor of p, so it would have to be 1 (since p is prime). But this contradicts our assumption that x₀ is not a fixed point of T_a.

In other words, the orbit contains exactly p distinct points. This holds for every orbit of S. Therefore, the set S, which contains a ^p − a points, can be broken up into orbits, each containing p points, so a ^p − a is divisible by p.

Proof using the Multinomial expansion

The proof is a very simple application of the Multinomial formula which is brought here for the sake of simplicity.

$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1,k_2,\ldots,k_m} {n \choose k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}.$

The summation is taken over all sequences of nonnegative integer indices k₁ through k_m such the sum of all k_i is n.

Thus if we express a as a sum of 1s (ones), we obtain

$a^p = \sum_{k_1,k_2,\ldots,k_a} {p \choose k_1, k_2, \ldots, k_a}$

Clearly, if p is prime, and if k_j not equal to p for any j, we have

${p \choose k_1, k_2, \ldots, k_a} \equiv 0 \pmod p \,\!$

and

${p \choose k_1, k_2, \ldots, k_a} \equiv 1 \pmod p \,\!$

if k_j equal to p for some j

Since there are exactly a elements such that k_j = p the theorem follows.