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 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 $a^p$ modulo , as one can check.

Secondly, it suffices to prove that
:$a^ \equiv 1 \pmod p$
for in the range . Indeed, if the previous assertion holds for such , multiplying both sides by yields the original form of the theorem,
:$a^p \equiv a \pmod p$
On the other hand, if or , 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

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 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 ''T''_''n''(''x''), where ''n'' ≥ 2 is an integer, mapping the interval , 1to itself by the formula
:$T_n(x) = \begin \ & 0 \leq x < 1, \\ 1 & x = 1, \end$
where 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 3 fixed points in the illustration above, and the same sort of 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_(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_(1).$
So let us assume that 0 ≤ ''x'' < 1. In this case,
:$T_n(x) = \ < 1,$
so ''T''_''m''(''T''_''n''(''x'')) is given by
:$T_m(T_n(x)) = \.$
Therefore, what we really need to show is that
:$\ = \.$
To do this we observe that = ''nx'' − ''k'', where ''k'' is the integer part of ''nx''; then
:$\ = \ = \,$
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'' ≥ 2. From Lemma 1, we know that it has ''a''^''p'' fixed points. By Lemma 2 we know that
:$T_(x) = \underbrace_,$
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_(x_0), T_(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''.

(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 , 1as 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..."). ''T''_''a''^''n'' 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 ''T''_''a''^''p'' can be thought of as the necklaces of length ''p'', with ''T''_''a''^''n'' 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 Euler_

Leonhard_Euler_(_,_;_15_April_170718_September_1783)_was_a_Swiss_mathematician,_physicist,_astronomer,_geographer,_logician_and_engineer_who_founded_the_studies_of_graph_theory_and_topology_and_made_pioneering_and_influential_discoveries_in_ma_...
,_uses_mathematical_induction.html" "title="Leonhard_Euler.html" "title=", 1); then ''T''_''n'' would only have ''n'' − 1 fixed points, but ''T''_''a''^''p'' − ''T''_''a'' would still work out to ''a''^''p'' − ''a'', as needed.)

Multinomial proofs

Proofs using the binomial theorem

Proof 1

This proof, due to Leonhard Euler">Euler