View source for Fermat's Little Theorem

'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].


== Statement ==

If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.

A frequently used corollary of Fermat's Little Theorem is <math>a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>.  The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.

This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>, where <math>\varphi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\varphi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].

In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.

== Proof ==
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem.  

=== Proof 1 (Induction) ===

The most straightforward way to prove this theorem is by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], 

<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center>

Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. 

Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired <math>\square</math>

=== Proof 2 (Inverses) ===

Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, 

<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br>

Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p},</math> which means <math>i = j</math> as <math>1 \leq i, j \leq p-1.</math> 

Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is 

<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br>

Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br>

A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math> <math>\square</math>

=== Proof 3 (Combinatorics) ===
<center><asy> 
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;
void necklace(pair k, pen colors[]){
 draw(shift(k)*unitcircle); 
 for(int i = 0; i < colors.length; ++i){
  pair p = k+expi(pi/2+2*pi*i/colors.length);
  fill(Circle(p,r),colors[i]);
  draw(Circle(p,r));
 }
}

pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center>

Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math> <math>\square</math>

[https://www.khanacademy.org/computing/computer-science/cryptography/random-algorithms-probability/v/fermat-s-little-theorem-visualization Video explanation]

=== Proof 4 (Geometry) ===
<center><asy>
void match(int i, int j){  
 draw(shift((i,j))*unitsquare,linewidth(1));
 draw(shift((j,i))*unitsquare,linewidth(1));
 draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));
}
int n = 6;
for(int i = 0; i < n; ++i){
 for(int j = 0; j < n; ++j)
  draw(shift((i,j))*unitsquare, linewidth(0.5));
}
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy>
import three; currentprojection = perspective(3,-2,4);
void match(int i, int j, int k){  
 draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));
 draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));
 draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));
 draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));
}
int n = 4;
for(int i = 0; i < n; ++i){
 for(int j = 0; j < n; ++j)
  for(int k = 0; k < n; ++k)
   draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));
}
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center>
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points 

<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br>

where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying 

<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br>

maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>p</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hypercube <math>\square</math>

=== Proof 5 (Burnside's Lemma) ===
Consider the number of ways to color a <math>p</math>-beaded oriented necklace in <math>a</math> colors up to symmetry where <math>p</math> is prime.  The group <math>C_p</math>, or the cyclic group of order <math>p</math>, acts on the <math>a</math> colorings of an oriented necklace by rotation.  The identity fixes all <math>a^p</math> of the colorings by definition.  If <math>g\in C_p</math> where <math>g\ne e</math> then <math>g</math> permutes the necklace in a single orbit which we can denote as <math>\mathcal{O}</math> (since the size of the orbit is a factor of <math>p</math>).  Hence, if <math>g\ne e</math> then <math>g</math> fixes only the <math>a</math> monochromatic paintings.  By [https://artofproblemsolving.com/wiki/index.php/Burnside%27s_Lemma Burnside's Lemma] the number of ways to paint the necklace (up to symmetry) is
<center><cmath>|\mathcal{O}|=\frac{1}{|G|}\sum_{g\in G}|\text{Fix}(g)|=\frac{1}{p}\sum_{g\in C_p}|\text{Fix}(g)|=\frac{1}{p}|\text{Fix}(e)|+\frac{1}{p}\sum_{g\in C_p}|\text{Fix}(g)|.</cmath></center><br>
This simplifies to
<center><cmath>\frac{a^p}{p}+\frac{a(p-1)}{p}=a+\frac{a^p-a}{p}</cmath></center><br>
and since <math>|\mathcal{O}|</math> must be an integer we must have that <math>a^p-a\mid p</math> or that <math>a^p-a\equiv 0 \pmod{p}\implies a^{p}\equiv a\pmod{p}</math> which finishes <math>\square</math> <math>\square</math>

===Proof 6 (Lagrange's Theorem)===
The key to this proof is to recognize that <math>(\mathbb{Z} / p\mathbb{Z})^{\times}</math> for some prime <math>p</math> where <math>(\mathbb{Z} / p\mathbb{Z})^{\times}=\{1,2,3,4,5,...p-1\}</math> is actually a group. Notice that the order of <math>(\mathbb{Z} / p\mathbb{Z})^{\times}</math> is <math>\varphi(p)=p-1</math>. Suppose there exists some <math>a\in(\mathbb{Z} / p\mathbb{Z})^{\times}</math> such that for some sufficient <math>k</math>, <math>a^k\equiv 1\pmod{p}</math>. By Lagrange's Theorem we must have that <math>k\,|\,p-1</math> so <math>p-1=km</math> for some <math>m</math>. Therefore we have
<center><cmath>a^{p-1}\equiv a^{km}\equiv (a^k)^m\equiv 1^m\equiv 1\pmod{p}</cmath></center><br>
which yields <math>a^p\equiv a\pmod{p}</math> as desired <math>\square</math>

===Proof 7 (Field Theory)===
Define a field <math>k</math> such that <math>k^{\times}</math> is its group of units written as <math>(k\backslash\{0\},\times)</math>.  If we can prove the cyclicity of <math>k^{\times}</math> then the claim follows.  We first prove the following lemma:

'''Lemma''': For any integer <math>n>1</math> and any finite field <math>k</math>, <math>C_n\times C_n</math> is not a subgroup of <math>k^{\times}</math>.

'''Proof''': Our aim is to show that <math>|C_n\times C_n|>|k^{\times}|</math>.  It is evident that any element in <math>C_n\times C_n</math> has to satisfy <math>x^n=1</math>.  However, at most <math>n</math> elements satisfy this equation (which can be proven inductively), and <math>|C_n\times C_n|=n^2</math> which means that it can not be a subgroup of <math>k^{\times}</math> since <math>|k^{\times}|=n</math>.  This completes the proof <math>\blacksquare</math>

Since <math>k^{\times}</math> is abelian, we can use the Fundamental Theorem of Finitely Generated Abelian Groups (FToFGAG) and we can write <math>k^{\times}</math> as a product of cyclic groups of prime order where the set of prime power orders is unique.  We can do this because if any two prime powers are not coprime then <math>k^{\times}</math> contains <math>C_{p^a}\times C_{p^b}</math> and consequently <math>C_p\times C_p</math>, contradicting our lemma.  We can therefore write <math>k^{\times}</math> as 
<center><cmath>k^{\times}\cong C_{p_{1}^{d_1}}\times C_{p_{2}^{d_2}}\times\ldots\times C_{p_{m}^{d_m}}</cmath></center><br>
where <math>p_1<p_2<p_3<\ldots p_m</math>.  By the [[Chinese Remainder Theorem]] we can then write
<cmath>k^{\times}\cong C_{p_{1}^{d_1}p_{2}^{d_2}\ldots p_{m}^{d_m}}</cmath>
which means <math>k^{\times}</math> is cyclic.  Our proof of Fermat's Little Theorem, however, comes as a corollary of this theorem.  If <math>k=\mathbb{Z}/p\mathbb{Z}</math> (which is always a field for prime <math>p</math>) then <math>k^{\times}</math> must be a cyclic group of order <math>p-1</math>.  Hence for any nonzero <math>a\in k</math>, <math>a^{p-1}=1</math> or that <math>a^{p}\equiv a\pmod{p}</math> for prime <math>p</math> which completes our work <math>\square</math>

== Problems ==
=== Introductory ===
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.

* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])
 
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).

=== Intermediate ===
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br>

*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#5])

=== Advanced ===
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>?  <br><br>

== Hints/Solutions ==
Introductory: 
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.

Intermediate:
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5.  Hence,<br>
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center>
<center><math>4 \equiv n\pmod{5}</math></center>
<br><br>
:Continuing, we examine the equation modulo 3,
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center>
<center><math>0 \equiv n\pmod{3}</math></center>

<br><br><br>
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5.  It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>.  It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.

Advanced:
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. 

==Extensions==

If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{(p-1)k}\equiv 1 \pmod {p}</math>. 

The above follows from the exponent rule <math>(a^b)^c=a^{bc}</math>

An extension of the Collary given above is that [https://artofproblemsolving.com/wiki/index.php/TOTO_SLOT_:_SITUS_TOTO_SLOT_MAXWIN_TERBAIK_DAN_TERPERCAYA TOTO SLOT] :
<cmath>(a^p)^w \equiv a^w \pmod {p}</cmath>

Immediately by normal exponent rules, it follows that if: <cmath>z=(d_1d_2\ldots d_f)_p</cmath> Then, <cmath>a^z\equiv a^{d_1+d_2+\cdots +d_f}\pmod p</cmath> Which means, by repeating the process, we have that we can reduce the exponent to its digital root base <math>p</math> . 




== See also ==
* [[Number theory]]
* [[Modular arithmetic]]
* [[Euler's Totient Theorem]]
* [[Order (group theory)]]

[[Category:Number theory]]
[[Category:Theorems]]