Proofs of Fermat's little theorem

Template:Short description 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).

SimplificationsEdit

Some of the proofs of Fermat's little theorem given below depend on two simplifications.

The first is that we may assume that Template:Mvar is in the range Template:Math. This is a simple consequence of the laws of modular arithmetic; we are simply saying that we may first reduce Template:Mvar modulo Template:Mvar. This is consistent with reducing <math>a^p </math> modulo Template:Mvar, as one can check.

Secondly, it suffices to prove that

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

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

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

On the other hand, if Template:Math, the theorem holds trivially.

Combinatorial proofsEdit

Proof by counting necklacesEdit

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.<ref>Template:Citation</ref>

To keep things simple, let us assume that Template:Mvar is a positive integer. Consider all the possible strings of Template:Math symbols, using an alphabet with Template:Mvar different symbols. The total number of such strings is Template:Math since there are Template:Mvar possibilities for each of Template:Mvar positions (see rule of product).

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

Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math,

Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math.

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

NecklacesEdit

File:Proofs-of-Fermats-Little-Theorem-bracelet1.svg

Necklace representing seven different strings (Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, Template:Math)

File:Proofs-of-Fermats-Little-Theorem-bracelet2.svg

Necklace representing only one string (Template:Math)

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:

Template:Math, Template:Math, Template:Math, Template:Math, Template:Math.

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

Template:Math, Template:Math, Template:Math, Template:Math, Template:Math,

Template:Math,

Template:Math.

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 Template:Math is divisible by Template:Math.

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

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

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

Template:Math,

Template:Math.

There aren't any others because Template:Mvar is exactly 3 symbols long and cannot be broken down into further repeating strings.

Completing the proofEdit

Using the above rule, we can complete the proof of Fermat's little theorem quite easily, as follows. Our starting pool of Template:Math strings may be split into two categories:

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

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

Proof using dynamical systemsEdit

This proof uses some basic concepts from dynamical systems.<ref>Template:Citation</ref>

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

<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 T₃(x) is illustrated below:

An example of a Tn function

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:

Fixed points of a Tn function

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,

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

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

so T_m(T_n(x)) is given by

Therefore, what we really need to show is that

To do this we observe that {nx} = 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

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

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.

Fixed points in the set S

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

<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 x₀ under T_a. 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 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 [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..."). T_aⁿ 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ⁿ 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 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 proofsEdit

Proofs using the binomial theoremEdit

Proof 1Edit

This proof, due to Euler,<ref name="Dickson"/> uses induction to prove the theorem for all integers Template:Math.

The base step, that Template:Math, is trivial. Next, we must show that if the theorem is true for Template:Math, then it is also true for Template:Math. For this inductive step, we need the following lemma.

Lemma. For any integers Template:Math and Template:Math and for any prime Template:Math, Template:Math.

The lemma is a case of the freshman's dream. Leaving the proof for later on, we proceed with the induction.

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

<math>(k+1)^p \equiv k^p + 1^p \pmod{p}.</math>

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

<math>(k+1)^p \equiv k + 1 \pmod{p},</math>

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,

<math>(x+y)^n=\sum_{i=0}^n{n \choose i}x^{n-i}y^i,</math>

where the coefficients are the binomial coefficients,

<math>{n \choose i}=\frac{n!}{i!(n-i)!},</math>

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

Proof of Lemma. We consider the binomial coefficient when the exponent is a prime p:

<math>{p \choose i}=\frac{p!}{i!(p-i)!}</math>

The binomial coefficients are all integers. The numerator contains a factor p by the definition of factorial. When 0 < i < p, neither of the terms in the denominator includes a factor of p (relying on the primality of p), leaving the coefficient itself to possess a prime factor of p from the numerator, implying that

<math>{p \choose i} \equiv 0 \pmod{p},\qquad 0 < i < p.</math>

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

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

<math>{4 \choose 2} = 6,</math>

which is not divisible by 4.

Proof 2Edit

Using the Lemma, we have:

<math>k^p \equiv ((k-1)+1)^p \equiv (k-1)^p + 1 \equiv ((k-2)+1)^p + 1 \equiv (k-2)^p + 2 \equiv \dots \equiv k \pmod{p}</math>.

Proof using the multinomial expansionEdit

The proof, which was first discovered by Leibniz (who did not publish it)<ref>Template:Citation</ref> and later rediscovered by Euler,<ref name="Dickson"/> is a very simple application of the multinomial theorem, which states

<math>(x_1 + x_2 + \cdots + x_m)^n

= \sum_{k_1,k_2,\dots,k_m \atop k_1+k_2+\dots+k_m=n} {n \choose k_1, k_2, \ldots, k_m}
x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}</math>

where

<math>{n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \dots k_m!}</math>

and the summation is taken over all sequences of nonnegative integer indices Template:Math such the sum of all Template:Math is Template:Math.

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

<math>a^p = (1 + 1 + ... + 1)^p

= \sum_{k_1,k_2,\dots,k_a \atop k_1+k_2+\dots+k_a=p} {p \choose k_1, k_2, \ldots, k_a}</math>

Clearly, if Template:Math is prime, and if Template:Math is not equal to Template:Math for any Template:Math, we have

<math>{p \choose k_1, k_2, \ldots, k_a} \equiv 0 \pmod p,</math>

and if Template:Math is equal to Template:Math for some Template:Math then

<math>{p \choose k_1, k_2, \ldots, k_a} = 1.</math>

Since there are exactly Template:Math elements such that Template:Math for some Template:Math, the theorem follows.

(This proof is essentially a coarser-grained variant of the necklace-counting proof given earlier; the multinomial coefficients count the number of ways a string can be permuted into arbitrary anagrams, while the necklace argument counts the number of ways a string can be rotated into cyclic anagrams. That is to say, that the nontrivial multinomial coefficients here are divisible by Template:Math can be seen as a consequence of the fact that each nontrivial necklace of length Template:Math can be unwrapped into a string in Template:Math many ways.

This multinomial expansion is also, of course, what essentially underlies the binomial theorem-based proof above)

Proof using power product expansionsEdit

An additive-combinatorial proof based on formal power product expansions was given by Giedrius Alkauskas.<ref>Template:Citation</ref> 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 theoremEdit

This proof,<ref name="Dickson">Template:Citation</ref><ref>Template:Citation</ref> discovered by James Ivory<ref>Template:Citation</ref> and rediscovered by Dirichlet,<ref>Template:Citation</ref> requires some background in modular arithmetic.

Let us assume that Template:Math is positive and not divisible by Template:Math.

The idea is that if we write down the sequence of numbers Template:NumBlk and reduce each one modulo Template:Math, the resulting sequence turns out to be a rearrangement of Template:NumBlk Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo Template:Math:

<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 Template:Math terms yields

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

Finally, we may “cancel out” the numbers Template:Math 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 (Template:EquationNote), reduced modulo Template:Mvar, are a rearrangement of (Template:EquationNote), 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 exampleEdit

If Template:Math and Template:Math, then the sequence in question is

reducing modulo 7 gives

which is just a rearrangement of

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 Template:Math and Template:Math.

The cancellation lawEdit

Let us first explain why it is valid, in certain situations, to “cancel”. The exact statement is as follows. If Template:Math, Template:Math, and Template:Math are integers, and Template:Math is not divisible by a prime number Template:Math, and if Template:NumBlk then we may “cancel” Template:Math to obtain Template:NumBlk Our use of this cancellation law in the above proof of Fermat's little theorem was valid because the numbers Template:Math are certainly not divisible by Template:Math (indeed they are smaller than Template:Math).

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

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

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

then we may “cancel” Template:Mvar to obtain

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

This follows from a generalization of Euclid's lemma.

The rearrangement propertyEdit

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 Template:Math, Template:Math, ..., Template:Math can be congruent to zero modulo Template:Math, since if Template:Math is one of the numbers Template:Math, then Template:Math is relatively prime with Template:Math, and so is Template:Math, so Euclid's lemma tells us that Template:Math shares no factor with Template:Math. Therefore, at least we know that the numbers Template:Math, Template:Math, ..., Template:Math, when reduced modulo Template:Math, must be found among the numbers Template:Math.

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

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

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

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

Since both Template:Math and Template:Math are between Template:Math and Template:Math, they must be equal. Therefore, the terms Template:Math, Template:Math, ..., Template:Math when reduced modulo Template:Math must be distinct. To summarise: when we reduce the Template:Math numbers Template:Math, Template:Math, ..., Template:Math modulo Template:Math, we obtain distinct members of the sequence Template:Math, Template:Math, ..., Template:Math. Since there are exactly Template:Math of these, the only possibility is that the former are a rearrangement of the latter.

Applications to Euler's theoremEdit

This method can also be used to prove Euler's theorem, with a slight alteration in that the numbers from Template:Math to Template:Math are substituted by the numbers less than and coprime with some number Template:Mvar (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 Template:Math, then the numbers less than Template:Math and coprime with Template:Math are Template:Math, Template:Math, Template:Math, and Template:Math. 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 criterionEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

Proofs using group theoryEdit

Standard proofEdit

This proof<ref>Template:Citation</ref> requires the most basic elements of group theory.

The idea is to recognise that the set Template:Math}, with the operation of multiplication (taken modulo Template:Math), forms a group. The only group axiom that requires some effort to verify is that each element of Template:Math is invertible. Taking this on faith for the moment, let us assume that Template:Math is in the range Template:Math, that is, Template:Math is an element of Template:Math. Let Template:Math be the order of Template:Math, that is, Template:Math is the smallest positive integer such that Template:Math. Then the numbers Template:Math reduced modulo Template:Math form a subgroup of Template:Math whose order is Template:Math and therefore, by Lagrange's theorem, Template:Math divides the order of Template:Math, which is Template:Math. So Template:Math for some positive integer Template:Math 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 Template:Math of Template:Math is invertible, we may proceed as follows. First, Template:Math is coprime to Template:Math. Thus Bézout's identity assures us that there are integers Template:Math and Template:Math such that Template:Math. Reading this equality modulo Template:Math, we see that Template:Math is an inverse for Template:Math, since Template:Math. Therefore, every element of Template:Math is invertible. So, as remarked earlier, Template:Math is a group.

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

Template:Math	1	2	3	4	5	6	7	8	9	10
Template:Math	1	6	4	3	9	2	8	7	5	10

Euler's proofEdit

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.<ref>Template:Citation</ref><ref>Template:Citation</ref> Let Template:Math be the set whose elements are the numbers Template:Math reduced modulo Template:Math. If Template:Math, then Template:Math and therefore Template:Math divides Template:Math. Otherwise, there is some Template:Math.

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

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

For instance, if Template:Math and Template:Math, then, since

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

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

we have Template:Math}. And now Template:Math.

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

NotesEdit