Fermat's Little Theorem
Fermat's little theorem is a fundamental theorem in elementary number theory, which helps compute powers of integers modulo prime numbers. It is a special case of Euler's theorem, and is important in applications of elementary number theory, including primality testing and public-key cryptography.
The result is called Fermat's "little theorem" in order to distinguish it from Fermat's last theorem.
(Fermat, 1640)
Let \(p\) be a prime number, and \(a\) be any integer. Then \(a^p-a\) is always divisible by \(p.\)
In modular arithmetic notation, this can be written as
\[a^p\equiv a \mod p. \]
\(11\) is prime, so \(2^{11}-2 = 2046\) is divisible by \(11\) by Fermat's little theorem.
Proofs of the Theorem
Fermat's little theorem can be deduced from the more general Euler's theorem, but there are also direct proofs of the result using induction and group theory.
Proof using Euler's theorem:
Let \(\phi\) be Euler's totient function. Euler's theorem says that \(a^{\phi(n)} \equiv 1 \pmod n,\) whenever \(a\) and \(n\) are coprime. Let \(n\) be a prime \(p.\) Then \(\phi(p)=p-1,\) so \(a^{p-1} \equiv 1 \pmod p\) for any \(a\) coprime to \(p.\) In this case, multiplying both sides by \(a\) gives \(a^p \equiv a\pmod p\) as desired.
On the other hand, if \(a\) is not coprime to \(p,\) then \(p|a.\) In this case, both \(a^p\) and \(a\) are congruent to \(0 \pmod p,\) so \(a^p \equiv a\pmod p\) here as well. \(_\square\)
Proof by induction:
First, we will show that the theorem is true for all positive integers \(a\) by induction. The base case \((\)when \(a=1)\) is obviously true: \(1^p\equiv 1 \pmod p.\)
For the inductive hypothesis, assume that \(a^p\equiv a\pmod{p}\) for a certain integer \(a\). The goal is to show that \((a+1)^p\equiv a+1 \pmod{p}.\)
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.\]
But \(p \big| {p\choose k}\) for \(1 \le k \le p-1\), because \(p\big|p!\) but \(p\nmid k!\) and \(p\nmid (p-k)!\). So the middle terms vanish mod \(p:\)
\[(a+1)^p\equiv a^p +1 \pmod{p}.\]
Substituting \(a^p\equiv a\pmod{p}\) by the inductive hypothesis gives \((a+1)^p\equiv a+1 \pmod{p}\).
So the result holds for all positive \(a\) by induction. But every integer is congruent mod \(p\) to a positive integer, so the result holds for every integer. \(_\square\)
Proof using Lagrange's theorem:
Suppose \(p \nmid a\) (as above, the other case is trivial). The set of powers of \(a\) forms a subgroup of \(({\mathbb Z}/p)^*\). Its size (or order) is the multiplicative order of \(a\); if it is \(x>0,\) the subgroup consists of the \(x\) elements \(\big\{1,a,a^2,\ldots,a^{x-1}\big\}.\) By Lagrange's theorem, \(x\) divides the order of \(({\mathbb Z}/p)^*,\) which is \(p-1.\) So \(xy=p-1\) for some integer \(y.\) Then
\[a^{p-1} \equiv a^{xy} \equiv (a^x)^y \equiv 1^y \equiv 1 \pmod p.\ _\square\]
This last proof actually generalizes to a proof of Euler's theorem.
A final proof is outlined in the following exercise:
Fermat's little theorem states that for prime \(p\), we have \(a^{p-1} \equiv 1\ (\mathrm{mod}\;p)\) \((p\not\mid a).\) Here is a proof:
- Consider \(1,2,\ldots,p-1\) and \(a,2a,\ldots,(p-1)a.\)
- They are permutations of each other under \(\mathrm{mod}\;p.\)
- \(1\cdot 2\cdots (p-1)\equiv a\cdot 2a \cdots (p-1)a \;(\mathrm{mod}\;p).\)
- Cancellation: \(1\equiv a^{p-1}\;(\mathrm{mod}\;p).\)
However, when we are talking about a composite number \(n\), we have \(a^{\phi(n)} \equiv 1\ (\mathrm{mod}\;n)\) for coprime integers \(a\) and \(n\) instead, from Euler's theorem.
If I use the above proof flow for the Euler's theorem, in which step do I first make a mistake?
Applications
If \(n \in \mathbb{N}\) and \(\gcd(n,35)=1\), prove that \(n^{12} \equiv 1 \pmod{35}.\)
By Fermat's little theorem, \(n^4 \equiv 1 \pmod 5\) and \(n^6 \equiv 1 \pmod 7\). So \( n^{12} \equiv 1 \pmod 5\) and \(n^{12} \equiv 1 \pmod 7.\) This implies \(n^{12} \equiv 1 \pmod {35}.\) \(_\square\)
See the wiki on primitive roots for a generalization of this argument.
What is the remainder of \(5^{119} \) upon division by 59?
By Fermat's little theorem, \( 5^{58} \equiv 1 \pmod{59},\) so \( 5^{116} \equiv 1 \pmod{59}, \) so \( 5^{119} \equiv 5^3 \equiv 7 \pmod{59}.\) \(_\square\)
\[\displaystyle { x }^{ 100 }-1\equiv \prod _{ i> 0 }^{ \quad }{ (x+{ a }_{ i }) } \pmod{101}\]
For positive integers \(a_i,\) consider the congruence above. Observe that these are linear factors, so a standard factorization for integers will not work \((\)in fact you'll have a \(50^\text{th}\) power in there\().\) Determine the minimum sum of all \({a}_{i}.\)
Let \(p>5\) be a prime number, and let \(k\) be any positive integer \(<p.\) Show that the decimal expansion of \( \frac{k}{p} \) consists of \(p-1\) repeating decimal digits.
By Fermat's little theorem, \( 10^{p-1} -1\) is divisible by \(p,\) say \(pa = 10^{p-1}-1.\) So
\[\frac{k}{p} = \frac{ka}{10^{p-1}-1} = ka\left( \frac1{10^{p-1}} + \frac1{10^{2(p-1)}} + \frac1{10^{3(p-1)}} + \cdots \right).\]
Since \(ka < pa < 10^{p-1},\) write \(ka \) as a \((p-1)\)-digit number (with 0s in the front if necessary). The above expansion shows that the \((p-1)\)-digit number will repeat in the decimal expansion.
For example, let \(k=2\) and \(p=7.\) Then \( a = \frac{10^6-1}7 = 142857,\) so \(ka = 285714.\) So
\[\begin{align} \frac27 = \frac{285714}{999999} &= 285714\left( \frac1{10^6} + \frac1{10^{12}} + \frac1{10^{18}} + \cdots \right) \\ &= 0.285714 + 0.000000285714 + 0.000000000000285714 + \cdots \\ &= 0.{\overline{285714}}.\ _\square \end{align}\]
Primality Testing and the Converse
Fermat's little theorem suggests a primality test: given \(n,\) pick a random small number \(a\) which is coprime to \(n\) and compute \(a^{n-1} \pmod n.\) If this is not \(1,\) then \(n\) is composite by Fermat's little theorem. If it is \(1,\) can we conclude that \(n\) is prime? In general, the answer is no. For instance, \( 2^{10} \equiv 1 \pmod{11}\) and \( 2^5 \equiv 1 \pmod{31}\) so \(2^{10} \equiv 1 \pmod{341},\) and therefore
\[2^{340} \equiv 1 \pmod{341}.\]
If \(n\) is composite but \(a^{n-1} \equiv 1\pmod n\) for some \(a\) coprime to \(n,\) then \(n\) is called a pseudoprime to base \(a.\) If \(n\) is a pseudoprime to every base relatively prime to it, it is called a Carmichael number. No iteration of this primality test will be able to distinguish Carmichael numbers from actual primes.
Nevertheless, a refinement of this idea due to Miller and Rabin gives an effective primality test in practice. See the Primality Testing wiki for a detailed discussion.
