Difference between revisions of "Fermat's Little Theorem"
Qkrwpwns12 (talk | contribs) m (→Statement) |
Scrabbler94 (talk | contribs) (Undo revision 215831 by Marianasinta (talk)) (Tag: Undo) |
||
(24 intermediate revisions by 16 users not shown) | |||
Line 3: | Line 3: | ||
== Statement == | == 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>. | 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>. | + | 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^{\ | + | 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. | In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations. | ||
Line 18: | Line 17: | ||
=== Proof 1 (Induction) === | === Proof 1 (Induction) === | ||
− | The most straightforward way to prove this theorem is | + | 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> | <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> | ||
Line 24: | 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 32: | Line 31: | ||
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br> | <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} | + | 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 | Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is | ||
Line 40: | 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 58: | 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] | ||
=== Proof 4 (Geometry) === | === Proof 4 (Geometry) === | ||
Line 96: | 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 | + | 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 == | == Problems == | ||
Line 109: | Line 135: | ||
* 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> | * 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 | + | *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 === | === Advanced === | ||
Line 132: | Line 158: | ||
Advanced: | 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]]. | * 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 Corollary given above is that: | ||
+ | <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 == | == See also == |
Latest revision as of 16:02, 8 May 2024
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 is an integer,
is a prime number and
is not divisible by
, then
.
A frequently used corollary of Fermat's Little Theorem is . As you can see, it is derived by multipling both sides of the theorem by
. The restated form is nice because we no longer need to restrict ourselves to integers
not divisible by
.
This theorem is a special case of Euler's Totient Theorem, which states that if and
are integers, then
, where
denotes Euler's totient function. In particular,
for prime numbers
. 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 . If
, then we can cancel a factor of
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 as a prime number. The base case,
, is obviously true. Suppose the statement
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.\]](http://latex.artofproblemsolving.com/7/d/9/7d97ae60aed64884958e9041c88f92b0b3e188d5.png)
Note that divides into any binomial coefficient of the form
for
. This follows by the definition of the binomial coefficient as
; since
is prime, then
divides the numerator, but not the denominator.
Taken , all of the middle terms disappear, and we end up with
. Since we also know that
, then
, as desired
Proof 2 (Inverses)
Let . Then, we claim that the set
, consisting of the product of the elements of
with
, taken modulo
, is simply a permutation of
. In other words,
![\[S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.\]](http://latex.artofproblemsolving.com/9/e/3/9e3fcc9c2595bb1f400d5eeda2f8b487a50c4d5c.png)
Clearly none of the for
are divisible by
, so it suffices to show that all of the elements in
are distinct. Suppose that
. Since
, by the cancellation rule, that reduces to
which means
as
Thus, , we have that the product of the elements of
is
![\[1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.\]](http://latex.artofproblemsolving.com/d/4/3/d43fce7dba53ee905ecec7abd530b71a0c3e9a2c.png)
Cancelling the factors from both sides, we are left with the statement
.
A similar version can be used to prove Euler's Totient Theorem, if we let
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]](http://latex.artofproblemsolving.com/8/e/1/8e1177baf35c15de796acc40c870b683f2eb3a90.png)
An illustration of the case
![$p=3,a=2$](http://latex.artofproblemsolving.com/3/9/5/395bf1abf4a50667434f990a011179ca36a1d049.png)
Consider a necklace with beads, each bead of which can be colored in
different ways. There are
ways to pick the colors of the beads.
of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly
more necklaces that are rotationally equivalent to this necklace. It follows that
must be divisible by
. Written in another way,
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]](http://latex.artofproblemsolving.com/7/a/f/7af624ebb7c7a4068b48928bb16dd155b06fc2a0.png)
![[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]](http://latex.artofproblemsolving.com/f/7/9/f79365d1a474b71898d433201404aec2f95b862a.png)
![$p=2,3$](http://latex.artofproblemsolving.com/b/d/7/bd70692c242910d2ed6a7fd7630cee3e320c6967.png)
![$a=6,4$](http://latex.artofproblemsolving.com/c/d/6/cd64f2455a41d0aaaa01f29c0341a1b57afc9f8e.png)
We imbed a hypercube of side length in
(the
-th dimensional Euclidean space), such that the vertices of the hypercube are at
. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of
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),\]](http://latex.artofproblemsolving.com/d/5/b/d5b02f8a513bb4a777ca2d9eb69e6a3826478cc0.png)
where each is an integer from
to
. Besides the
centers of the unit hypercubes in the main diagonal (from
to
), the transformation carrying
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 , from which it follows that
. 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
Proof 5 (Burnside's Lemma)
Consider the number of ways to color a -beaded oriented necklace in
colors up to symmetry where
is prime. The group
, or the cyclic group of order
, acts on the
colorings of an oriented necklace by rotation. The identity fixes all
of the colorings by definition. If
where
then
permutes the necklace in a single orbit which we can denote as
(since the size of the orbit is a factor of
). Hence, if
then
fixes only the
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)|.\]](http://latex.artofproblemsolving.com/9/1/f/91fbafdbc3b1706a07eac3b006ae4db5d701f2b2.png)
This simplifies to
![\[\frac{a^p}{p}+\frac{a(p-1)}{p}=a+\frac{a^p-a}{p}\]](http://latex.artofproblemsolving.com/3/c/1/3c1ba225036c4882981c24484c685a84ac199fe5.png)
and since must be an integer we must have that
or that
which finishes
Proof 6 (Lagrange's Theorem)
The key to this proof is to recognize that for some prime
where
is actually a group. Notice that the order of
is
. Suppose there exists some
such that for some sufficient
,
. By Lagrange's Theorem we must have that
so
for some
. Therefore we have
![\[a^{p-1}\equiv a^{km}\equiv (a^k)^m\equiv 1^m\equiv 1\pmod{p}\]](http://latex.artofproblemsolving.com/7/e/1/7e17cfb95c804109ee4849ecfcbb394fe443d7c4.png)
which yields as desired
Proof 7 (Field Theory)
Define a field such that
is its group of units written as
. If we can prove the cyclicity of
then the claim follows. We first prove the following lemma:
Lemma: For any integer and any finite field
,
is not a subgroup of
.
Proof: Our aim is to show that . It is evident that any element in
has to satisfy
. However, at most
elements satisfy this equation (which can be proven inductively), and
which means that it can not be a subgroup of
since
. This completes the proof
Since is abelian, we can use the Fundamental Theorem of Finitely Generated Abelian Groups (FToFGAG) and we can write
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
contains
and consequently
, contradicting our lemma. We can therefore write
as
![\[k^{\times}\cong C_{p_{1}^{d_1}}\times C_{p_{2}^{d_2}}\times\ldots\times C_{p_{m}^{d_m}}\]](http://latex.artofproblemsolving.com/d/5/a/d5a89e1cba36565844f543928dcbba07a2c33aae.png)
where . By the Chinese Remainder Theorem we can then write
which means
is cyclic. Our proof of Fermat's Little Theorem, however, comes as a corollary of this theorem. If
(which is always a field for prime
) then
must be a cyclic group of order
. Hence for any nonzero
,
or that
for prime
which completes our work
Problems
Introductory
- Compute some examples, for example find
, and
, and check your answers by calculator where possible.
- Let
. What is the units digit of
? (2008 AMC 12A Problems/Problem 15)
- Find
mod
. (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
. Find the value of
. (1989 AIME, #9)
- If
, find the last two digits of
. (2008 PUMaC, NT A#5)
Advanced
- Is it true that if
is a prime number, and
is an integer
, then the sum of the products of each
-element subset of
will be divisible by
?
Hints/Solutions
Introductory:
- Hint: For the first example, we have
by FLT (Fermat's Little Theorem). It follows that
.
Intermediate:
- Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders
can have after division by certain numbers. By Fermat's Little Theorem, we know
is congruent to
modulo 5. Hence,
![$3 + 0 + 4 + 7 \equiv n\pmod{5}$](http://latex.artofproblemsolving.com/9/a/e/9ae6c19669910fdcb79f9ce3947ec835f29f0733.png)
![$4 \equiv n\pmod{5}$](http://latex.artofproblemsolving.com/0/1/3/01340d89f298149cc82f56f121d194fd13476f30.png)
- Continuing, we examine the equation modulo 3,
![$-1 + 1 + 0 + 0 \equiv n\pmod{3}$](http://latex.artofproblemsolving.com/c/4/c/c4ce449e7b124ba4e09da16e3c97742a85d3ad9c.png)
![$0 \equiv n\pmod{3}$](http://latex.artofproblemsolving.com/1/2/d/12dfbd3baa056d0fc22f91f6486c78285ec22d0b.png)
- Thus,
is divisible by three and leaves a remainder of four when divided by 5. It's obvious that
, so the only possibilities are
or
. It quickly becomes apparent that 174 is much too large, so
must be 144.
Advanced:
- Hint: try to establish the identity
, and then apply Vieta's formulas.
Extensions
If is an integer,
is a prime number and
is not divisible by
, then
.
The above follows from the exponent rule
An extension of the Corollary given above is that:
Immediately by normal exponent rules, it follows that if: Then,
Which means, by repeating the process, we have that we can reduce the exponent to its digital root base
.