6.2 Fermat’s Little Theorem
Polynomials of high degree
Lagrange’s Theorem tells us nothing new about polynomials \(f(x)\) of degree \(d\geq p\): there are only \(p\) classes in \({\mathbb Z}_p\), so it is trivial that at most \(d\) classes satisfy \(f(x)\equiv 0\).
The following result, useful in studying polynomials of high degree, is known as Fermat’s Little Theorem (not to be confused with Fermat’s Last Theorem).
If \(p\) is prime and \(a\not\equiv 0\text{ mod }(p)\), then \(a^{p-1}\equiv 1\text{ mod }(p)\).
We give Proof B from (Jones and Jones 2006), which is purely number-theoretic.
Proof. The integers \(1, 2, \ldots, p-1\) form a complete set of non-zero residues \(\text{mod }(p)\). If \(a\not\equiv 0\text{ mod }(p)\) then \(xa\equiv ya\) implies \(x\equiv y\), by Corollary 5.32, so that the integers \(a, 2a, \ldots, (p-1)a\) lie in distinct classes \(\text{mod }(p)\). None of these integers is divisible by \(p\), so they also form a complete set of non-zero residues.
It follows that \(a, 2a, \ldots, (p-1)a\) are congruent to \(1, 2, \ldots, p-1\) in some order. (For instance, if \(p=5\) and \(a=3\) then multiplying the residues \(1, 2, 3, 4\) by \(3\) we get \(3, 6, 9, 12\), which are respectively congruent to \(3, 1, 4, 2\).) The products of these two sets of integers must therefore lie in the same class, that is, \[1\times 2\times \cdots\times (p-1)\equiv a\times 2a\times \cdots\times (p-1)a\;\;\text{ mod }(p)\,,\] or equivalently \[(p-1)!\equiv (p-1)!\,a^{p-1}\;\;\text{ mod }(p)\,.\] Rearranging, we get \[ (p-1)!\left(1-a^{p-1}\right)\equiv0\text{ mod }p \] so since \(p\) and \((p-1)!\) are coprime, then we see from Lemma 5.35 (2) that \(1\equiv a^{p-1}\text{ mod }p\).
Theorem 6.4 states that all the classes in \({\mathbb Z}_p\) except \([0]\) are roots of the polynomial \(x^{p-1}-1\).
If \(p\) is prime then \(a^p\equiv a\text{ mod }(p)\) for every integer \(a\).
Proof. If \(a\not\equiv 0\) then Theorem 6.4 gives \(a^{p-1}\equiv 1\), so multiplying each side by \(a\) gives the result. If \(a\equiv 0\) then \(a^p\equiv 0\) also, so the result is again true.
Since \(23\) is prime and \(3\) is not divisible by \(23\), we can apply Theorem 6.4 with \(p=23\) and \(a=3\), so that \(3^{22}\equiv 1\text{ mod }(23)\). Now \(67=22\times 3+1\), so \[3^{67}=(3^{22})^3\times 3^{1}\equiv 1^3\times 3^{1}\equiv 3^{1}=3\text{ mod }(23)\,.\]
Show that \(a^{25}-a\) is divisible by \(30\) for every integer \(a\).
Here Corollary 6.5 is more appropriate, since it refers to all integers \(a\), rather than just those coprime to \(p\). By factorising \(30\), we see that it is sufficient to prove that \(a^{25}-a\) is divisible by each of the primes \(p=2, 3\) and \(5\). Remember that \(p|a^{25}-a\) if and only if \(a^{25}-a\equiv0\text{ mod }p\) if and only if \(a^{25}\equiv a\text{ mod }p\).
Let us deal with \(p=5\) first. Applying Corollary 6.5 twice, we have \[a^{25}=(a^5)^5\equiv a^5\equiv a\;\;\text{ mod }(5)\,,\] so \(5\) divides \(a^{25}-a\) for all \(a\). Similarly \(a^3\equiv a\text{ mod }(3)\), so \[a^{25}=(a^3)^8a\equiv a^8a=a^9=(a^3)^3\equiv a^3\equiv a\;\;\text{ mod }(3)\,,\] as required.
For \(p=2\) a direct argument easily shows that \(a^{25}-a\) is always even, but we can also continue with this method and use \(a^2\equiv a \text{ mod }(2)\) to deduce (rather laboriously) that \[a^{25}=(a^2)^{12}a\equiv a^{12}a=(a^2)^6a=a^6a=\] \[(a^2)^3a\equiv a^3a=a^4=(a^2)^2\equiv a^2\equiv a\;\;\text{ mod }(2)\,.\]
Find the least non-negative residue of \(3^{91}\text{ mod }(23)\).
Corollary 6.5 shows that if \(f(x)\) is any polynomial of degree \(d\geq p\), then by repeatedly replacing any occurrence of \(x^p\) with \(x\) we can find a polynomial \(g(x)\) of degree less than \(p\) with the property that \(f(x)\equiv g(x)\) for all integers \(x\). In other words, when considering polynomials \(\text{mod }(p)\), it is sufficient to restrict attention to those of degree \(d<p\). Similarly, the coefficients can also be simplified by reducing them \(\text{mod }(p)\).
Let us find all the roots of the congruence \[f(x)=x^{17}+6x^{14}+2x^5+1\equiv 0\;\;\text{ mod }(5)\,.\]
Here \(p=5\), so by replacing \(x^5\) with \(x\) we can replace the leading term \(x^{17}=(x^5)^3x^2\) with \(x^3x^2=x^5\), and hence with \(x\). Similarly \(x^{14}\) is replaced with \(x^2\), and \(x^5\) with \(x\), so giving the polynomial \(x+6x^2+2x+1\). Reducing the coefficients \(\text{mod }(5)\) gives \(x^2+3x+1\). Thus \(f(x)\equiv 0\) is equivalent to the much simpler congruence \[g(x)=x^2+3x+1\equiv 0\;\;\text{ mod }(5)\,.\]
Here we can simply try all five classes \([x]\in{\mathbb Z}_5\), or else note that \(g(x)\equiv(x-1)^2\); either way, we find that \([x]=[1]\) is the only root of \(g(x)\equiv 0\), so this class is the only root of \(f(x)\equiv 0\).
As another application of Fermat’s Little Theorem, we prove a result known as Wilson’s Theorem, though it was first proved by Lagrange in 1770:
An integer \(n>1\) is prime if and only if \((n-1)!\equiv-1\text{ mod }(n)\).
Proof. Suppose that \(n\) is a prime \(p\). If \(p=2\) then \((p-1)!=1\equiv -1\text{ mod }(p)\), as required, so we may assume that \(p\) is odd. Define \[f(x)=(1-x)(2-x)\ldots(p-1-x)+1-x^{p-1}\,,\] a polynomial with integer coefficients. This has degree \(d<p-1\), since when the product is expanded, the two terms in \(f(x)\) involving \(x^{p-1}\) cancel. If \(a=1, 2, \ldots, p-1\) then \(f(a)\equiv 0\text{ mod }(p)\): the product \((1-a)(2-a)\ldots(p-1-a)\) vanishes since it has a factor equal to \(0\), and \(1-a^{p-1}\equiv 0\) by Fermat’s Little Theorem.
Thus \(f(x)\) has more than \(d\) roots \(\text{mod }(p)\), so by Corollary 6.3 its coefficients are all congruent to \(0\) mod \(p\). In particular, the constant term \((p-1)!+1\equiv0\text{ mod }p\), so \((p-1)!\equiv -1\).
For the converse, suppose that \((n-1)!\equiv -1\text{ mod }(n)\). We then have \((n-1)!\equiv -1\text{ mod }(m)\) for any factor \(m\) of \(n\). If \(m<n\) then \(m\) appears as a factor of \((n-1)!\), so \((n-1)!\equiv 0\text{ mod }(m)\) and hence \(-1\equiv 0\text{ mod }(m)\). This implies that \(m=1\), so we conclude that \(n\) has no proper factors and is therefore prime.
In principle Wilson’s theorem gives a method for checking whether or not a number is prime, but in practice it is infeasible for large numbers. The run time of an algorithm based on the theorem (or the storage requirement if it is parallelised) grows very fast with the size of \(n\).
In 2003 the Indian mathematician Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal announced that they had discovered an efficient algorithm for deterministic primality testing. Their paper is only 9 pages long and you can read about it on the web at http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
Use Euclid’s theorem and Wilson’s theorem to evaluate\[\gcd(29!+29,30!+29).\]
Recall from Exercise 6.2 we saw that the polynomial \(x^2+1\) in \(\mathbb Z_p\) has roots: \[ \begin{array}{r|l} p&\text{roots}\\\hline 2&1\\ 3&\\ 5&2\text{ and }3\\ 7&\\ 11&\\ 13&5\text{ and }8\\ 17&4\text{ and }13\\ \end{array} \]