Proofs of Fermat's little theorem

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

:<math>a^p \equiv a \pmod p</math>

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 is in the range . This is a simple consequence of the laws of modular arithmetic; we are simply saying that we may first reduce modulo . This is consistent with reducing <math>a^p </math> modulo , as one can check.

Secondly, it suffices to prove that

:<math>a^{p-1} \equiv 1 \pmod p</math>

for in the range . Indeed, if the previous assertion holds for such , multiplying both sides by yields the original form of the theorem,

:<math>a^p \equiv a \pmod p </math>

On the other hand, if , the theorem holds trivially.

Combinatorial proofs

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 is a positive integer. Consider all the possible strings of symbols, using an alphabet with different symbols. The total number of such strings is since there are possibilities for each of positions (see rule of product).

For example, if and , then we can use an alphabet with two symbols (say and ), and there are strings of length 5:

: , , , , , , , ,

: , , , , , , , .

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

Necklaces

frame|right|class=skin-invert-image|Necklace representing seven different strings (, , , , , , )

frame|right|class=skin-invert-image|Necklace representing only one string ()

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:

: , , , , .

In full, each line of the following list corresponds to a single necklace, and the entire list comprises all 32 strings.

: ,

: , , , , ,

: .

Notice that in the above list, each necklace with more than one symbol is represented by 5 different strings, and the number of necklaces represented by just one string is 2, i.e. is the number of distinct symbols. Thus the list shows very clearly why is divisible by .

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

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

For example, suppose we start with the string , which is built up of several copies of the shorter string . If we rotate it one symbol at a time, we obtain the following 3 strings:

: ,

: .

There aren't any others because is exactly 3 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 strings may be split into two categories:

Some strings contain identical symbols. There are exactly of these, one for each symbol in the alphabet. (In our running example, these are the strings and .)
The rest of the strings use at least two distinct symbols from the alphabet. If we can break up a given string into repeating copies of some string , the length of must divide the length of . But since the length of is the prime , the only possible length for is also . Therefore, the above rule tells us that has exactly friends (including itself).

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

Proof using dynamical systems

This proof uses some basic concepts from dynamical systems.

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

:<math>T_n(x) = \begin{cases}

\{ nx \} & 0 \leq x < 1, \\

1 & x = 1,

\end{cases}</math>

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

200px|center|class=skin-invert-image|An example of a Tn function

A number x0 is said to be a fixed point of a function f(x) if f(x0) = x0; in other words, if f leaves x0 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 T3(x) are 0, 1/2, and 1; they are marked by black circles on the following diagram:

180px|center|class=skin-invert-image|Fixed points of a Tn function

We will require the following two lemmas.

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

Proof. There are 3 fixed points in the illustration above, corresponding to the intervals <math>[0,\tfrac13),[\tfrac13.\tfrac23),[\tfrac23,1]</math> of , and the same geometrical argument applies for all <math>n\ge2</math>.

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

:<math>T_m(T_n(x)) = T_{mn}(x).</math>

In other words, Tmn(x) is the composition of Tn(x) and Tm(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

:<math>T_m(T_n(1)) = T_m(1) = 1 = T_{mn}(1).</math>

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

:<math>T_n(x) = \{nx\} < 1, </math>

so Tm(Tn(x)) is given by

:<math>T_m(T_n(x)) = \{m\{nx\}\}.</math>

Therefore, what we really need to show is that

:<math>\{m\{nx\}\} = \{mnx\}.</math>

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

:<math>\{m\{nx\}\} = \{mnx - mk\} = \{mnx\},</math>

since mk is an integer.

Now let us properly begin the proof of Fermat's little theorem, by studying the function Tap(x). We will assume that a ≥ 2. From Lemma 1, we know that it has ap fixed points. By Lemma 2 we know that

:<math>T_{a^p}(x) = \underbrace{T_a(T_a( \cdots T_a(x) \cdots ))}_{p\text{ times,</math>

so any fixed point of Ta(x) is automatically a fixed point of Tap(x).

We are interested in the fixed points of Tap(x) that are not fixed points of Ta(x). Let us call the set of such points S. There are ap − a points in S, because by Lemma 1 again, Ta(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 32 − 3 = 6.

250px|center|class=skin-invert-image|Fixed points in the set S

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

:<math> x_0, T_a(x_0), T_a(T_a(x_0)), T_a(T_a(T_a(x_0))), \ldots. </math>

This sequence is called the orbit of x0 under Ta. By Lemma 2, this sequence can be rewritten as

:<math> x_0, T_a(x_0), T_{a^2}(x_0), T_{a^3}(x_0), \ldots. </math>

Since we are assuming that x0 is a fixed point of Ta p(x), after p steps we hit Tap(x0) = x0, 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 x0 is not a fixed point of Ta.

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

(This proof is essentially the same as the necklace-counting proof given above, simply viewed through a different lens: one may think of the interval [0, 1] as given by sequences of digits in base a (our distinction between 0 and 1 corresponding to the familiar distinction between representing integers as ending in ".0000..." and ".9999..."). Tan amounts to shifting such a sequence by n many digits. The fixed points of this will be sequences that are cyclic with period dividing n. In particular, the fixed points of Tap can be thought of as the necklaces of length p, with Tan corresponding to rotation of such necklaces by n spots.

This proof could also be presented without distinguishing between 0 and 1, simply using the half-open interval [0, 1); then Tn would only have n − 1 fixed points, but Tap − Ta would still work out to ap − a, as needed.)

Multinomial proofs

Proofs using the binomial theorem

Proof 1

This proof, due to Euler, and later rediscovered by Euler, This proof uses neither the Euclidean algorithm nor the binomial theorem, but rather it employs formal power series with rational coefficients.

Proof as a particular case of Euler's theorem

This proof, discovered by James Ivory and rediscovered by Dirichlet, requires some background in modular arithmetic.

Let us assume that is positive and not divisible by .

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

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

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

:<math>a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots \times (p-1) \pmod p.</math>

Collecting together the terms yields

:<math>a^{p-1} (p-1)! \equiv (p-1)! \pmod p.</math>

Finally, we may “cancel out” the numbers from both sides of this equation, obtaining

:<math>a^{p-1} \equiv 1 \pmod p.</math>

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

Why the elements of the sequence (), reduced modulo , are a rearrangement of (), 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 and , then the sequence in question is

:<math>3, 6, 9, 12, 15, 18;</math>

reducing modulo 7 gives

:<math>3, 6, 2, 5, 1, 4,</math>

which is just a rearrangement of

:<math>1, 2, 3, 4, 5, 6.</math>

Multiplying them together gives

:<math>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;</math>

that is,

:<math>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.</math>

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

:<math>3^6 \equiv 1 \pmod 7, </math>

which is Fermat's little theorem for the case and .

The cancellation law

Let us first explain why it is valid, in certain situations, to “cancel”. The exact statement is as follows. If , , and  are integers, and is not divisible by a prime number , and if

then we may “cancel” to obtain

Our use of this cancellation law in the above proof of Fermat's little theorem was valid because the numbers are certainly not divisible by (indeed they are smaller than ).

We can prove the cancellation law easily using Euclid's lemma, which generally states that if a prime divides a product (where and are integers), then must divide or . Indeed, the assertion () simply means that divides . Since is a prime which does not divide , Euclid's lemma tells us that it must divide instead; that is, () holds.

Note that the conditions under which the cancellation law holds are quite strict, and this explains why Fermat's little theorem demands that is a prime. For example, , but it is not true that . However, the following generalization of the cancellation law holds: if , , , and are integers, if and are relatively prime, and if

:<math>ux \equiv uy \pmod z,</math>

then we may “cancel” to obtain

:<math>x \equiv y \pmod z.</math>

This follows from a generalization of Euclid's lemma.

The rearrangement property

Finally, we must explain why the sequence

:<math>a, 2a, 3a, \ldots, (p-1)a, </math>

when reduced modulo p, becomes a rearrangement of the sequence

:<math>1, 2, 3, \ldots, p-1.</math>

To start with, none of the terms , , ..., can be congruent to zero modulo , since if is one of the numbers , then is relatively prime with , and so is , so Euclid's lemma tells us that shares no factor with . Therefore, at least we know that the numbers , , ..., , when reduced modulo , must be found among the numbers .

Furthermore, the numbers , , ..., must all be distinct after reducing them modulo , because if

:<math>ka \equiv ma \pmod p, </math>

where and are one of , then the cancellation law tells us that

:<math>k \equiv m \pmod p. </math>

Since both and are between and , they must be equal. Therefore, the terms , , ..., when reduced modulo must be distinct.

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

Applications to Euler's theorem

This method can also be used to prove Euler's theorem, with a slight alteration in that the numbers from to are substituted by the numbers less than and coprime with some number (not necessarily prime). Both the rearrangement property and the cancellation law (under the generalized form mentioned above) are still satisfied and can be utilized.

For example, if , then the numbers less than  and coprime with are , , , and . Thus we have:

:<math>a \times 3a \times 7a \times 9a \equiv 1 \times 3 \times 7 \times 9 \pmod {10}. </math>

Therefore,

:<math>{a^{\varphi(10) \equiv 1 \pmod {10}. </math>

Proof as a corollary of Euler's criterion

Proofs using group theory

Standard proof

This proof requires the most basic elements of group theory.

The idea is to recognise that the set }, with the operation of multiplication (taken modulo ), forms a group. The only group axiom that requires some effort to verify is that each element of is invertible. Taking this on faith for the moment, let us assume that is in the range , that is, is an element of . Let be the order of , that is, is the smallest positive integer such that . Then the numbers reduced modulo  form a subgroup of  whose order is  and therefore, by Lagrange's theorem, divides the order of , which is . So for some positive integer and then

:<math>a^{p-1} \equiv a^{km} \equiv (a^k)^m \equiv 1^m \equiv 1 \pmod p. </math>

To prove that every element of is invertible, we may proceed as follows. First, is coprime to . Thus Bézout's identity assures us that there are integers and such that . Reading this equality modulo , we see that is an inverse for , since . Therefore, every element of is invertible. So, as remarked earlier, is a group.

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

:{| border="1" cellspacing="0" cellpadding="8"

| align="center" |

| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10

| align="center" |

| 1 || 6 || 4 || 3 || 9 || 2 || 8 || 7 || 5 || 10

Euler's proof

If we take the previous proof and, instead of using Lagrange's theorem, we try to prove it in this specific situation, then we get Euler's third proof, which is the one that he found more natural. Let be the set whose elements are the numbers reduced modulo . If , then and therefore divides . Otherwise, there is some .

Let be the set whose elements are the numbers reduced modulo . Then has distinct elements because otherwise there would be two distinct numbers } such that , which is impossible, since it would follow that . On the other hand, no element of can be an element of , because otherwise there would be numbers } such that , and then , which is impossible, since .

So, the set has elements. If it turns out to be equal to G, then and therefore divides . Otherwise, there is some and we can start all over again, defining as the set whose elements are the numbers reduced modulo . Since is finite, this process must stop at some point and this proves that divides .

For instance, if and , then, since

we have and }. Clearly, }. Let be an element of ; for instance, take . Then, since

we have }. Clearly, . Let be an element of ; for instance, take . Then, since

we have }. And now .

Note that the sets , , and so on are in fact the cosets of in .