Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Fermat's Little Theorem"

m
(Added another proof using Lagrange's Theorem.)
Line 23: Line 23:
 
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.  
 
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. 
+
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) ===
 
=== Proof 2 (Inverses) ===
Line 39: Line 39:
 
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>
 
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>.
+
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) ===
 
=== Proof 3 (Combinatorics) ===
Line 57: Line 57:
 
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center>
 
</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>.
+
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]
 
[https://www.khanacademy.org/computing/computer-science/cryptography/random-algorithms-probability/v/fermat-s-little-theorem-visualization Video explanation]
Line 97: Line 97:
 
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br>
 
<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.
+
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 (Group Theory) ===
+
=== 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
 
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>
 
<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>
Line 105: Line 105:
 
<center><cmath>\frac{a^p}{p}+\frac{a(p-1)}{p}=a+\frac{a^p-a}{p}</cmath></center><br>
 
<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>
 
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>
 +
 +
===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>
  
 
== Problems ==
 
== Problems ==

Revision as of 16:08, 8 December 2021

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 ${a}$ is an integer, ${p}$ is a prime number and ${a}$ is not divisible by ${p}$, then $a^{p-1}\equiv 1 \pmod {p}$.

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

This theorem is a special case of Euler's Totient Theorem, which states that if $a$ and $n$ are integers, then $a^{\varphi(n)} \equiv 1 \pmod{n}$, where $\varphi(n)$ denotes Euler's totient function. In particular, $\varphi(p) = p-1$ for prime numbers $p$. 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 $a^p \equiv a \pmod{p}$. If $\text{gcd}\,(a,p) = 1$, then we can cancel a factor of $a$ from both sides and retrieve the first version of the theorem.

Proof 1 (Induction)

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

\[(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.\]

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

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

Proof 2 (Inverses)

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

\[S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.\]


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

Thus, $\mod{p}$, we have that the product of the elements of $S$ is

\[1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.\]


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

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

Proof 3 (Combinatorics)

[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]
An illustration of the case $p=3,a=2$.

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

Video explanation

Proof 4 (Geometry)

[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]     [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 $p=2,3$ and $a=6,4$, respectively.

We imbed a hypercube of side length $a$ in $\mathbb{R}^p$ (the $p$-th dimensional Euclidean space), such that the vertices of the hypercube are at $(\pm a/2,\pm a/2, \ldots, \pm a/2)$. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of $a^p$ separate unit hypercubes, with centers consisting of the points

\[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),\]


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

\[P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)\]

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 $p$, from which it follows that $a^p \equiv a \pmod{p}$. 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 $\square$

Proof 5 (Burnside's Lemma)

Consider the number of ways to color a $p$-beaded oriented necklace in $a$ colors up to symmetry where $p$ is prime. The group $C_p$, or the cyclic group of order $p$, acts on the $a$ colorings of an oriented necklace by rotation. The identity fixes all $a^p$ of the colorings by definition. If $g\in C_p$ where $g\ne e$ then $g$ permutes the necklace in a single orbit which we can denote as $\mathcal{O}$ (since the size of the orbit is a factor of $p$). Hence, if $g\ne e$ then $g$ fixes only the $a$ monochromatic paintings. By Burnside's Lemma the number of ways to paint the necklace (up to symmetry) is

\[|\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)|.\]


This simplifies to

\[\frac{a^p}{p}+\frac{a(p-1)}{p}=a+\frac{a^p-a}{p}\]


and since $|\mathcal{O}|$ must be an integer we must have that $a^p-a\mid p$ or that $a^p-a\equiv 0 \pmod{p}\implies a^{p}\equiv a\pmod{p}$ which finishes $\square$

Proof 6 (Lagrange's Theorem)

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

\[a^{p-1}\equiv a^{km}\equiv (a^k)^m\equiv 1^m\equiv 1\pmod{p}\]


which yields $a^p\equiv a\pmod{p}$ as desired $\square$

Problems

Introductory

  • Compute some examples, for example find $3^{31} \pmod{7}, 29^{25} \pmod{11}$, and $128^{129} \pmod{17}$, and check your answers by calculator where possible.

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 $133^5+110^5+84^5+27^5=n^5$. Find the value of ${n}$. (1989 AIME, #9)

Advanced

  • Is it true that if $p$ is a prime number, and $k$ is an integer $2 \le k \le p$, then the sum of the products of each $k$-element subset of $\{1, 2, \ldots, p\}$ will be divisible by $p$?

Hints/Solutions

Introductory:

  • Hint: For the first example, we have $3^6 \equiv 1 \pmod{7}$ by FLT (Fermat's Little Theorem). It follows that $3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}$.

Intermediate:

  • Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders $n$ can have after division by certain numbers. By Fermat's Little Theorem, we know ${n^{5}}$ is congruent to $n$ modulo 5. Hence,
$3 + 0 + 4 + 7 \equiv n\pmod{5}$
$4 \equiv n\pmod{5}$



Continuing, we examine the equation modulo 3,
$-1 + 1 + 0 + 0 \equiv n\pmod{3}$
$0 \equiv n\pmod{3}$




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

Advanced:

Extensions

If ${a}$ is an integer, ${p}$ is a prime number and ${a}$ is not divisible by ${p}$, then $a^{(p-1)k}\equiv 1 \pmod {p}$.

The above follows from the exponent rule $(a^b)^c=a^{bc}$

An extension of the Collary given above is that : \[(a^p)^w \equiv a^w \pmod {p}\]

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



See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&oldid=167511"