Proofs of Fermat's little theorem

2025-02-19T17:09:41Z

23.84.110.223: /* Simplifications */

{{Short description|none}} 
This article collects together a variety of [[mathematical proof|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 {{mvar|a}} is in the range {{math|0 ≤ ''a'' ≤ ''p'' − 1}}. This is a simple consequence of the laws of [[modular arithmetic]]; we are simply saying that we may first reduce {{mvar|a}} modulo {{mvar|p}}. This is consistent with reducing <math>a^p </math> modulo {{mvar|p}}, as one can check.

Secondly, it suffices to prove that
:<math>a^{p-1} \equiv 1 \pmod p</math>
for {{mvar|a}} in the range {{math|1 ≤ ''a'' ≤ ''p'' − 1}}. Indeed, if the previous assertion holds for such {{mvar|a}}, multiplying both sides by {{math|''a''}} yields the original form of the theorem,
:<math>a^p \equiv a \pmod p </math>
On the other hand, if {{math|''a'' {{=}} 0}}, 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 [[Double counting (proof technique)|counting a collection of objects in two different ways]]).

The proof given here is an adaptation of [[Solomon W. Golomb|Golomb]]'s proof.<ref>{{Citation|last = Golomb|first = Solomon W.|author-link = Solomon W. Golomb|url = http://www.cimat.mx/~mmoreno/teaching/spring08/Fermats_Little_Thm.pdf|title = Combinatorial proof of Fermat's "Little" Theorem|journal = [[American Mathematical Monthly]]|volume = 63|issue = 10|year =1956|pages = 718|jstor = 2309563|doi = 10.2307/2309563}}</ref>

To keep things simple, let us assume that {{mvar|a}} is a [[positive integer]]. Consider all the possible [[string (computer science)|strings]] of {{math|''p''}} symbols, using an [[alphabet]] with {{mvar|a}} different symbols. The total number of such strings is {{math|''ap''}} since there are {{mvar|a}} possibilities for each of {{mvar|p}} positions (see [[rule of product]]).

For example, if {{math|''p'' {{=}} 5}} and {{math|''a'' {{=}} 2}}, then we can use an alphabet with two symbols (say {{mvar|A}} and {{mvar|B}}), and there are {{math|25 {{=}} 32}} strings of length 5:
: {{math|''AAAAA''}}, {{math|''AAAAB''}}, {{math|''AAABA''}}, {{math|''AAABB''}}, {{math|''AABAA''}}, {{math|''AABAB''}}, {{math|''AABBA''}}, {{math|''AABBB''}},
: {{math|''ABAAA''}}, {{math|''ABAAB''}}, {{math|''ABABA''}}, {{math|''ABABB''}}, {{math|''ABBAA''}}, {{math|''ABBAB''}}, {{math|''ABBBA''}}, {{math|''ABBBB''}},
: {{math|''BAAAA''}}, {{math|''BAAAB''}}, {{math|''BAABA''}}, {{math|''BAABB''}}, {{math|''BABAA''}}, {{math|''BABAB''}}, {{math|''BABBA''}}, {{math|''BABBB''}},
: {{math|''BBAAA''}}, {{math|''BBAAB''}}, {{math|''BBABA''}}, {{math|''BBABB''}}, {{math|''BBBAA''}}, {{math|''BBBAB''}}, {{math|''BBBBA''}}, {{math|''BBBBB''}}.

We will argue below that if we remove the strings consisting of a single symbol from the list (in our example, {{math|''AAAAA''}} and {{math|''BBBBB''}}), the remaining {{math|''ap'' − ''a''}} strings can be arranged into groups, each group containing exactly {{mvar|p}} strings. It follows that {{math|''ap'' − ''a''}} is divisible by {{mvar|p}}.

====Necklaces====
[[Image:Proofs-of-Fermats-Little-Theorem-bracelet1.svg|frame|right|Necklace representing seven different strings ({{math|''ABCBAAC''}}, {{math|''BCBAACA''}}, {{math|''CBAACAB''}}, {{math|''BAACABC''}}, {{math|''AACABCB''}}, {{math|''ACABCBA''}}, {{math|''CABCBAA''}})]]
[[Image:Proofs-of-Fermats-Little-Theorem-bracelet2.svg|frame|right|Necklace representing only one string ({{math|''AAAAAAA''}})]]

Let us think of each such string as representing a [[necklace (combinatorics)|necklace]]. That is, we connect the two ends of the string together and regard two strings as the same necklace if we can [[circular shift|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:
: {{math|''AAAAB''}}, {{math|''AAABA''}}, {{math|''AABAA''}}, {{math|''ABAAA''}}, {{math|''BAAAA''}}.
In full, each line of the following list corresponds to a single necklace, and the entire list comprises all 32 strings.
: {{math|''AAAAB''}}, {{math|''AAABA''}}, {{math|''AABAA''}}, {{math|''ABAAA''}}, {{math|''BAAAA''}},
: {{math|''AAABB''}}, {{math|''AABBA''}}, {{math|''ABBAA''}}, {{math|''BBAAA''}}, {{math|''BAAAB''}},
: {{math|''AABAB''}}, {{math|''ABABA''}}, {{math|''BABAA''}}, {{math|''ABAAB''}}, {{math|''BAABA''}},
: {{math|''AABBB''}}, {{math|''ABBBA''}}, {{math|''BBBAA''}}, {{math|''BBAAB''}}, {{math|''BAABB''}},
: {{math|''ABABB''}}, {{math|''BABBA''}}, {{math|''ABBAB''}}, {{math|''BBABA''}}, {{math|''BABAB''}},
: {{math|''ABBBB''}}, {{math|''BBBBA''}}, {{math|''BBBAB''}}, {{math|''BBABB''}}, {{math|''BABBB''}},
: {{math|''AAAAA''}},
: {{math|''BBBBB''}}.
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 {{math|32 − 2}} is divisible by {{math|5}}.

One can use the following rule to work out how many friends a given string {{math|''S''}} has:
: If {{math|''S''}} is built up of several copies of the string {{math|''T''}}, and {{math|''T''}} cannot itself be broken down further into repeating strings, then the number of friends of {{math|''S''}} (including {{math|''S''}} itself) is equal to the ''length'' of {{math|''T''}}.

For example, suppose we start with the string {{math|''S'' {{=}} ''ABBABBABBABB''}}, which is built up of several copies of the shorter string {{math|''T'' {{=}} ''ABB''}}. If we rotate it one symbol at a time, we obtain the following 3 strings:
: {{math|''ABBABBABBABB''}},
: {{math|''BBABBABBABBA''}},
: {{math|''BABBABBABBAB''}}.
There aren't any others because {{mvar|ABB}} 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 {{math|''a p''}} strings may be split into two categories:
* Some strings contain {{mvar|p}} identical symbols. There are exactly {{mvar|a}} of these, one for each symbol in the alphabet. (In our running example, these are the strings {{mvar|AAAAA}} and {{mvar|BBBBB}}.)
* The rest of the strings use at least two distinct symbols from the alphabet. If we can break up a given string {{mvar|S}} into repeating copies of some string {{mvar|T}}, the length of {{mvar|T}} must divide the length of {{mvar|S}}. But since the length of {{mvar|S}} is the prime {{mvar|p}}, the only possible length for {{mvar|T}} is also {{mvar|p}}. Therefore, the above rule tells us that {{mvar|S}} has exactly {{mvar|p}} friends (including {{mvar|S}} itself).

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

===Proof using dynamical systems===
This proof uses some basic concepts from [[dynamical system]]s.<ref>{{Citation|last = Iga|first = Kevin|title = A Dynamical Systems Proof of Fermat's Little Theorem|journal = [[Mathematics Magazine]]|volume = 76|issue = 1|year = 2003|pages = 48–51|doi = 10.2307/3219132|jstor = 3219132}}</ref>

We start by considering a family of [[function (mathematics)|functions]] ''T''''n''(''x''), where ''n'' ≥ 2 is an [[integer]], mapping the [[interval (mathematics)|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''3(''x'') is illustrated below:

[[Image:Proofs-of-Fermats-Little-Theorem-dynamic1.png|200px|center|An example of a ''T''''n'' function]]

A number ''x''0 is said to be a ''[[fixed point (mathematics)|fixed point]]'' of a function ''f''(''x'') if ''f''(''x''0) = ''x''0; in other words, if ''f'' leaves ''x''0 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 a function|graph]] of ''f''(''x'') intersects the graph of the line ''y'' = ''x''. For example, the fixed points of the function ''T''3(''x'') are 0, 1/2, and 1; they are marked by black circles on the following diagram:

[[Image:Proofs-of-Fermats-Little-Theorem-dynamic2.png|180px|center|Fixed points of a ''T''''n'' 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,
:<math>T_m(T_n(x)) = T_{mn}(x).</math>
In other words, ''T''''mn''(''x'') is the [[function composition|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
:<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 ''T''''m''(''T''''n''(''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 ''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 32 − 3 = 6.

[[Image:Proofs-of-Fermats-Little-Theorem-dynamic3.png|250px|center|Fixed points in the set ''S'']]

The main idea of the proof is now to split the set ''S'' up into its [[orbit (dynamics)|orbits]] under ''T''''a''. What this means is that we pick a point ''x''0 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''0 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''0 is a fixed point of ''T''''a'' ''p''(''x''), after ''p'' steps we hit ''T''''a''''p''(''x''0) = ''x''0, 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''0 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 [[#Proof by counting necklaces|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''''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 [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 proofs===

====Proofs using the binomial theorem====

====Proof 1====

This proof, due to [[Leonhard Euler|Euler]],<ref name="Dickson"/> uses [[mathematical induction|induction]] to prove the theorem for all integers {{math|''a'' ≥ 0}}.

The base step, that {{math|0''p'' ≡ 0 (mod ''p'')}}, is trivial. Next, we must show that if the theorem is true for {{math|''a'' {{=}} ''k''}}, then it is also true for {{math|''a'' {{=}} ''k'' + 1}}. For this inductive step, we need the following lemma.

'''Lemma'''. For any integers {{math|''x''}} and {{math|''y''}} and for any prime {{math|''p''}}, {{math|(''x'' + ''y'')''p'' ≡ ''xp'' + ''yp'' (mod ''p'')}}.

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 

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

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 expansion====
The proof, which was first discovered by [[Gottfried Wilhelm Leibniz|Leibniz]] (who did not publish it)<ref>{{Citation|last = Vacca|first = Giovanni|author-link = Giovanni Vacca (mathematician)|journal = Bibliotheca Mathematica| series = 2nd series|volume = 8|issue = 2|pages = 46–48|language = it|year = 1894|title = Intorno alla prima dimostrazione di un teorema di Fermat}}</ref> and later rediscovered by [[Leonhard Euler|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 {{math|''k''1, ''k''2, ..., ''km''}} such the sum of all {{math|''ki''}} is {{math|''n''}}.

Thus if we express {{math|''a''}} 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 {{math|''p''}} is prime, and if {{math|''kj''}} is not equal to {{math|''p''}} for any {{math|''j''}}, we have

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

and if {{math|''kj''}} is equal to {{math|''p''}} for some {{math|''j''}} then

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

Since there are exactly {{math|''a''}} elements such that {{math|''kj'' {{=}} ''p''}} for some {{math|''j''}}, the theorem follows.

(This proof is essentially a coarser-grained variant of the [[#Proof by counting necklaces|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 {{math|''p''}} can be seen as a consequence of the fact that each nontrivial necklace of length {{math|''p''}} can be unwrapped into a string in {{math|''p''}} many ways.

This multinomial expansion is also, of course, what essentially underlies the [[#Proofs using the binomial theorem|binomial theorem-based proof]] above)

===Proof using power product expansions===

An additive-combinatorial proof based on formal power product expansions was given by Giedrius Alkauskas.<ref>{{Citation|last = Alkauskas|first = Giedrius|arxiv = 0801.0805|title = A Curious Proof of Fermat's Little Theorem|journal = [[American Mathematical Monthly]]|volume = 116|issue = 4|year = 2009|pages = 362–364|jstor = 40391097|doi=10.4169/193009709x470236}}</ref> This proof uses neither the [[Euclidean algorithm]] nor the [[binomial theorem]], but rather it employs [[formal power series]] with [[rational number|rational]] coefficients.

==Proof as a particular case of Euler's theorem==
This proof,<ref name="Dickson">{{Citation|last = Dickson|first = Leonard Eugene|author-link = Leonard Eugene Dickson|title = History of the Theory of Numbers| volume = I|chapter = Fermat's and Wilson's theorems, generalizations, and converses; symmetric functions of {{math|1, 2, ..., ''p'' − 1}} modulo {{math|''p''}}|publisher = [[Dover Publications|Dover]]|isbn = 978-0-486-44232-7|year = 2005|orig-year = 1919|zbl = 1214.11001|title-link = History of the Theory of Numbers}}</ref><ref>{{Citation|last = Hardy|first = G. H.|author-link = G. H. Hardy|last2 = Wright|first2 = E. M.|author2-link = E. M. Wright|publisher = [[Oxford University Press]]|year = 2008|edition = 6th|chapter = Fermat's Theorem and its Consequences|title = An Introduction to the Theory of Numbers|isbn = 978-0-19-921986-5|title-link = An Introduction to the Theory of Numbers}}</ref> discovered by [[James Ivory (mathematician)|James Ivory]]<ref>{{Citation|last = Ivory|first = James|author-link = James Ivory (mathematician)|journal = The Mathematical Repository |series=New Series|year = 1806|volume = 1|issue = II|pages = 6–8|title = Demonstration of a theorem respecting prime numbers}}</ref> and rediscovered by [[Peter Gustav Lejeune Dirichlet|Dirichlet]],<ref>{{Citation|last = Lejeune Dirichlet|first = Peter Gustav|author-link = Peter Gustav Lejeune Dirichlet|journal = [[Crelle's Journal|Journal für die reine und angewandte Mathematik]]|year = 1828|volume = 3|pages = 390–393|title = Démonstrations nouvelles de quelques théorèmes relatifs aux nombres|language = fr}}</ref> requires some background in [[modular arithmetic]].

Let us assume that {{math|''a''}} is positive and not divisible by {{math|''p''}}.

The idea is that if we write down the sequence of numbers
{{NumBlk|:|<math>a, 2a, 3a, \ldots, (p-1)a</math>|{{EquationRef|A}}}}
and reduce each one modulo {{math|''p''}}, the resulting sequence turns out to be a rearrangement of
{{NumBlk|:|<math>1, 2, 3, \ldots, p-1.</math>|{{EquationRef|B}}}}
Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo {{math|''p''}}:
:<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 {{math|''a''}} terms yields
:<math>a^{p-1} (p-1)! \equiv (p-1)! \pmod p.</math>
Finally, we may “cancel out” the numbers {{math|1, 2, ..., ''p'' − 1}} 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 ({{EquationNote|A}}), reduced modulo {{mvar|p}}, are a rearrangement of ({{EquationNote|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 {{math|''a'' {{=}} 3}} and {{math|''p'' {{=}} 7}}, 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 {{math|''a'' {{=}} 3}} and {{math|''p'' {{=}} 7}}.

===The cancellation law===

Let us first explain why it is valid, in certain situations, to “cancel”. The exact statement is as follows. If {{math|''u''}}, {{math|''x''}}, and {{math|''y''}} are integers, and {{math|''u''}} is not divisible by a prime number {{math|''p''}}, and if
{{NumBlk|:|<math>ux \equiv uy \pmod p,</math>|{{EquationRef|C}}}}
then we may “cancel” {{math|''u''}} to obtain
{{NumBlk|:|<math>x \equiv y \pmod p.</math>|{{EquationRef|D}}}}
Our use of this '''cancellation law''' in the above proof of Fermat's little theorem was valid because the numbers {{math|1, 2, ..., ''p'' − 1}} are certainly not divisible by {{math|''p''}} (indeed they are ''smaller'' than {{math|''p''}}).

We can prove the cancellation law easily using [[Euclid's lemma]], which generally states that if a prime {{math|''p''}} divides a product {{math|''ab''}} (where {{math|''a''}} and {{math|''b''}} are integers), then {{math|''p''}} must divide {{math|''a''}} or {{math|''b''}}. Indeed, the assertion ({{EquationNote|C}}) simply means that {{math|''p''}} divides {{math|''ux'' − ''uy'' {{=}} ''u''(''x'' − ''y'')}}. Since {{math|''p''}} is a prime which does not divide {{math|''u''}}, Euclid's lemma tells us that it must divide {{math|''x'' − ''y''}} instead; that is, ({{EquationNote|D}}) holds.

Note that the conditions under which the cancellation law holds are quite strict, and this explains why Fermat's little theorem demands that {{mvar|p}} is a prime. For example, {{math|2×2 ≡ 2×5 (mod 6)}}, but it is not true that {{math|2 ≡ 5 (mod 6)}}. However, the following generalization of the cancellation law holds: if {{mvar|u}}, {{mvar|x}}, {{mvar|y}}, and {{mvar|z}} are integers, if {{mvar|u}} and {{mvar|z}} are [[Coprime integers|relatively prime]], and if
:<math>ux \equiv uy \pmod z,</math>
then we may “cancel” {{mvar|''u''}} to obtain
:<math>x \equiv y \pmod z.</math>
This follows from a [[Euclid's lemma#Proof|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 {{math|''a''}}, {{math|2''a''}}, ..., {{math|(''p'' − 1)''a''}} can be congruent to zero modulo {{math|''p''}}, since if {{math|''k''}} is one of the numbers {{math|1, 2, ..., ''p'' − 1}}, then {{math|''k''}} is relatively prime with {{math|''p''}}, and so is {{math|''a''}}, so [[Euclid's lemma]] tells us that {{math|''ka''}} shares no factor with {{math|''p''}}. Therefore, at least we know that the numbers {{math|''a''}}, {{math|2''a''}}, ..., {{math|(''p'' − 1)''a''}}, when reduced modulo {{math|''p''}}, must be found among the numbers {{math|1, 2, 3, ..., ''p'' − 1}}.

Furthermore, the numbers {{math|''a''}}, {{math|2''a''}}, ..., {{math|(''p'' − 1)''a''}} must all be ''distinct'' after reducing them modulo {{math|''p''}}, because if
:<math>ka \equiv ma \pmod p, </math>
where {{math|''k''}} and {{math|''m''}} are one of {{math|1, 2, ..., ''p'' − 1}}, then the cancellation law tells us that
:<math>k \equiv m \pmod p. </math>
Since both {{math|''k''}} and {{math|''m''}} are between {{math|1}} and {{math|''p'' − 1}}, they must be equal. Therefore, the terms {{math|''a''}}, {{math|2''a''}}, ..., {{math|(''p'' − 1)''a''}} when reduced modulo {{math|''p''}} must be distinct.
To summarise: when we reduce the {{math|''p'' − 1}} numbers {{math|''a''}}, {{math|2''a''}}, ..., {{math|(''p'' − 1)''a''}} modulo {{math|''p''}}, we obtain distinct members of the sequence {{math|1}}, {{math|2}}, ..., {{math|''p'' − 1}}. Since there are exactly {{math|''p'' − 1}} 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 {{math|1}} to {{math|''p'' − 1}} are substituted by the numbers less than and coprime with some number {{mvar|m}} (not necessarily prime). Both the rearrangement property and the cancellation law (under the generalized form mentioned [[#The cancellation law|above]]) are still satisfied and can be utilized.

For example, if {{math|''m'' {{=}} 10}}, then the numbers less than {{math|''m''}} and coprime with {{math|''m''}} are {{math|1}}, {{math|3}}, {{math|7}}, and {{math|9}}. 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==

{{main|Euler's criterion#Alternative proof}}

==Proofs using group theory==

===Standard proof===
This proof<ref>{{Citation|last = Weil|first = André|author-link = André Weil|last2 = Rosenlicht|first2 = Maxwell|author-link2 = Maxwell Rosenlicht|title = Number Theory for beginners|year = 1979|publisher = [[Springer Science+Business Media|Springer-Verlag]]|isbn = 978-0-387-90381-1|doi = 10.1007/978-1-4612-9957-8|section = § VIII|zbl = 0405.10001|url-access = registration|url = https://archive.org/details/numbertheoryforb0000weil}}</ref> requires the most basic elements of [[group theory]].

The idea is to recognise that the set {{math|''G'' {{=}} {1, 2, ..., ''p'' − 1}}}, with the operation of multiplication (taken modulo {{math|''p''}}), forms a [[group (mathematics)|group]]. The only group axiom that requires some effort to verify is that each element of {{math|''G''}} is invertible. Taking this on faith for the moment, let us assume that {{math|''a''}} is in the range {{math|1 ≤ ''a'' ≤ ''p'' − 1}}, that is, {{math|''a''}} is an element of {{math|''G''}}. Let {{math|''k''}} be the [[order (group theory)|order]] of {{math|''a''}}, that is, {{math|''k''}} is the smallest positive integer such that {{math|''ak'' ≡ 1 (mod ''p'')}}. Then the numbers {{math|1, ''a'', ''a''2, ..., ''a''''k'' −1}} reduced modulo {{math|''p''}} form a [[subgroup]] of {{math|''G''}} whose [[Order (group theory)|order]] is {{math|''k''}} and therefore, by [[Lagrange's theorem (group theory)|Lagrange's theorem]], {{math|''k''}} divides the order of {{math|''G''}}, which is {{math|''p'' − 1}}. So {{math|''p'' − 1 {{=}} ''km''}} for some positive integer {{math|''m''}} 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 {{math|''b''}} of {{math|''G''}} is invertible, we may proceed as follows. First, {{math|''b''}} is [[Coprime integers|coprime]] to {{math|''p''}}. Thus [[Bézout's identity]] assures us that there are integers {{math|''x''}} and {{math|''y''}} such that {{math|''bx'' + ''py'' {{=}} 1}}. Reading this equality modulo {{math|''p''}}, we see that {{math|''x''}} is an inverse for {{math|''b''}}, since {{math|''bx'' ≡ 1 (mod ''p'')}}. Therefore, every element of {{math|''G''}} is invertible. So, as remarked earlier, {{math|''G''}} is a group.

For example, when {{math|''p'' {{=}} 11}}, the inverses of each element are given as follows:
:{| border="1" cellspacing="0" cellpadding="8"
| align="center" | {{math|''a''}}
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| align="center" | {{math|''a'' −1}}
| 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.<ref>{{Citation|last = Weil|first = André|author-link = André Weil|title = Number theory: An approach through history; from Hammurapi to Legendre|publisher = [[Birkhäuser]]|year = 2007|isbn = 978-0-8176-4565-6|section = § III.VI|zbl = 1149.01013|orig-year = 1984}}</ref><ref>{{Citation|last = Euler|first = Leonhard|author-link = Leonhard Euler|title = Theoremata circa residua ex divisione potestatum relicta|language = la|url = http://math.dartmouth.edu/~euler/docs/originals/E262.pdf|journal = Novi Commentarii Academiae Scientiarum Petropolitanae|volume = 7|year = 1761|pages = 49–82}}</ref> Let {{math|''A''}} be the set whose elements are the numbers {{math|1, ''a'', ''a''2, ..., ''a''''k'' − 1}} reduced modulo {{math|''p''}}. If {{math|''A'' {{=}} ''G''}}, then {{math|''k'' {{=}} ''p'' − 1}} and therefore {{math|''k''}} divides {{math|''p'' −1}}. Otherwise, there is some {{math|''b''1 ∈ ''G''\''A''}}.

Let {{math|''A''1}} be the set whose elements are the numbers {{math|''b''1, ''ab''1, ''a''2''b''1, ..., ''a''''k'' − 1''b''1}} reduced modulo {{math|''p''}}. Then {{math|''A''1}} has {{math|''k''}} distinct elements because otherwise there would be two distinct numbers {{math|''m'', ''n'' ∈ {0, 1, ..., ''k'' − 1}}} such that {{math|''amb''1 ≡ ''anb''1 (mod ''p'')}}, which is impossible, since it would follow that {{math|''am'' ≡ ''an'' (mod ''p'')}}. On the other hand, no element of {{math|''A''1}} can be an element of {{math|''A''}}, because otherwise there would be numbers {{math|''m'', ''n'' ∈ {0, 1, ..., ''k'' − 1}}} such that {{math|''amb''1 ≡ ''an'' (mod ''p'')}}, and then {{math|''b''1 ≡ ''ana''''k'' − ''m'' ≡ ''a''''n'' + ''k'' − ''m'' (mod ''p'')}}, which is impossible, since {{math|''b''1 ∉ ''A''}}.

So, the set {{math|''A''∪''A''1}} has {{math|2''k''}} elements. If it turns out to be equal to ''G'', then {{math|2''k'' {{=}} ''p'' −1}} and therefore {{math|''k''}} divides {{math|''p'' −1}}. Otherwise, there is some {{math|''b''2 ∈ ''G''\(''A''∪''A''1)}} and we can start all over again, defining {{math|''A''2}} as the set whose elements are the numbers {{math|''b''2, ''ab''2, ''a''2''b''2, ..., ''a''''k'' − 1''b''2}} reduced modulo {{math|''p''}}. Since {{math|''G''}} is finite, this process must stop at some point and this proves that {{math|''k''}} divides {{math|''p'' − 1}}.

For instance, if {{math|''a'' {{=}} 5}} and {{math|''p'' {{=}} 13}}, then, since
* {{math|52 {{=}} 25 ≡ 12 (mod 13)}},
* {{math|53 {{=}} 125 ≡ 8 (mod 13)}},
* {{math|54 {{=}} 625 ≡ 1 (mod 13)}},
we have {{math|''k'' {{=}} 4}} and {{math|''A'' {{=}} {1, 5, 8, 12}}}. Clearly, {{math|''A'' ≠ ''G'' {{=}} {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}}}. Let {{math|''b''1}} be an element of {{math|''G''\''A''}}; for instance, take {{math|''b''1 {{=}} 2}}. Then, since
* {{math|2×1 {{=}} 2}},
* {{math|2×5 {{=}} 10}},
* {{math|2×8 {{=}} 16 ≡ 3 (mod 13)}},
* {{math|2×12 {{=}} 24 ≡ 11 (mod 13)}},
we have {{math|''A''1 {{=}} {2, 3, 10, 11}}}. Clearly, {{math|''A''∪''A''1 ≠ ''G''}}. Let {{math|''b''2}} be an element of {{math|''G''\(''A''∪''A''1)}}; for instance, take {{math|''b''2 {{=}} 4}}. Then, since
* {{math|4×1 {{=}} 4}},
* {{math|4×5 {{=}} 20 ≡ 7 (mod 13)}},
* {{math|4×8 {{=}} 32 ≡ 6 (mod 13)}},
* {{math|4×12 {{=}} 48 ≡ 9 (mod 13)}},
we have {{math|''A''2 {{=}} {4, 6, 7, 9}}}. And now {{math|''G'' {{=}} ''A''∪''A''1∪''A''2}}.

Note that the sets {{math|''A''}}, {{math|''A''1}}, and so on are in fact the [[coset]]s of {{math|''A''}} in {{math|''G''}}.

==Notes==
<references />

{{DEFAULTSORT:Fermat's Little Theorem, Proofs Of}}
[[Category:Modular arithmetic]]
[[Category:Number theory]]
[[Category:Article proofs]]

Vero - Wikipedia - User contributions [en]

Proofs of Fermat's little theorem