Section 12.1 Finding More Primes
As we have seen, it is not terribly hard to find lots of small primes. One can use
Sieve of Eratosthenes, or make numbers coprime to known primes and then factor them.
The problem is that almost every effort to find lots of big primes has been stymied. Primes simply do not follow nice enough rules to enable easy detection, despite the fact that they seem to follow very nice rules on average – a fact we will explore in later chapters.
Subsection 12.1.1 Fermat primes
Here is an interesting historical example. Recall (
Subsection 11.5.1) that our friend Pierre de Fermat thought that numbers of the form
\(2^{2^n}+1\) would always be prime – numbers such as
\(5\text{,}\) \(17\text{,}\) and
\(257\text{.}\)
Definition 12.1.1.
We call numbers of the form \(F_n=2^{2^n}+1\) Fermat numbers.
However, as we mentioned in
Subsection 11.5.1, in 1732 Euler proved that
\(F_n\) is not prime if
\(n=5\text{.}\) (See William Dunham’s
[E.5.5] for an engaging take on the story.) Evaluate the following cell, which quickly produces numbers a bit long for print!
For example,
\begin{equation*}
2^{2^7}+1 = 59649589127497217\cdot 5704689200685129054721\text{.}
\end{equation*}
Nobody knows if there are any more primes
1 in the sequence
\(F_n\) past
\(n=4\text{.}\) Even the prime factors of elements of the sequence seem to be
quite large; see for instance the end of
Subsection 12.6.1 for
\(F_8\text{,}\) or
Subsection 17.5.2 for even more information. A very accessible article about the properties a prime divisor of a Fermat number is
[E.7.43], where the authors prove directly that
\(37\) can never divide any
\(F_n\text{.}\)
There is a special test called Pépin’s test that tests Fermat numbers for primality. It is equivalent to checking whether
\(3\) is a primitive root of
\(2^{2^n}+1\text{.}\) Proving it is just a little beyond us right now, so we will not address it yet; see
Fact 17.5.1 for the statement and proof.
Subsection 12.1.2 Primes from Fermat numbers
However, we can at least prove what seems obvious in the computation after
Definition 12.1.1 – namely, that lots of primes arise as factors of Fermat numbers, even when
\(F_n\) isn’t itself prime. First, we need a lemma.
Lemma 12.1.2.
Suppose \(\ell=jk\) is even, and \(k\) is an even factor. Then \(2^\ell-1\) factors as
\begin{equation*}
2^\ell-1=2^{jk}-1=\left(2^j+1\right)\left(\left(2^j\right)^{k-1}-\left(2^j\right)^{k-2}+\left(2^j\right)^{k-3}-\cdots+\left(2^j\right)-1\right)
\end{equation*}
Proof.
Example 12.1.3.
For instance, \(2^6-1=63\) factors as
\begin{equation*}
2^{3\cdot 2}-1=(2^3+1)(2^3-1)
\end{equation*}
which corresponds to the factorization \(9\cdot 7\text{.}\)
Similarly, \(2^{12}-1=4095\) factors as
\begin{equation*}
2^{3\cdot 4}-1=(2^3+1)(2^9-2^6+2^3-1)
\end{equation*}
which corresponds to the factorization \(9\cdot 455\text{.}\)
Proposition 12.1.4. Fermat numbers are coprime.
\(F_n=2^{2^n}+1\) and \(F_m=2^{2^m}+1\) are coprime if \(m\neq n\text{.}\)
Proof.
First, notice that any two Fermat numbers are very closely related to each other; if \(n<m\text{,}\) then \(F_n-1\) divides \(F_m-1\text{.}\) In fact, one is a power of the other:
\begin{equation*}
2^{2^m}=\left(2^{2^n}\right)^{2^{m-n}}
\end{equation*}
Because of this, using
Lemma 12.1.2 with
\(j=2^n\) and
\(k=2^{m-n}\) (which is certainly even), we get
\begin{equation*}
2^{2^m}-1=\left(2^{2^n}+1\right)\left(\left(2^{2^n}\right)^{2^{m-n}-1}-\left(2^{2^n}\right)^{2^{m-n}-2}+\cdots +\left(2^{2^n}\right)^1-1 \right)
\end{equation*}
This implies the divisibility relationship
\begin{equation*}
F_n=2^{2^n}+1\mid 2^{2^m}-1=F_m-2
\end{equation*}
so any number
\(d\) that divides
\(F_n\) also divides
\(F_m-2\text{.}\) Now we do a standard trick (see also
Exercise 2.5.6). Combine all of the above facts to see that any divisor of
\(F_n\) which also divides
\(F_m\) must divide
\(F_m-(F_m-2)=2\text{,}\) so a common divisor of
\(F_n\) and
\(F_m\) could only be two or one.
But both Fermat numbers are odd, so the gcd must be 1.
Subsection 12.1.3 Mersenne primes
Another early attempt at finding big primes was an idea of Marin Mersenne.
Mersenne suggested
6 that one try searching for primes of the form
\(2^p-1\text{,}\) where
\(p\) is itself prime.
Definition 12.1.6.
In general, numbers of the form \(M_n=2^n-1\) are called Mersenne numbers. If they are prime, they are called Mersenne primes.
Using a variant of
Lemma 12.1.2 (see
Exercise 12.7.2), it is not too hard to prove that if
\(n\) is composite then
\(M_n\) is too; see
Exercise 12.7.7. Further, not every
\(M_p\) for prime
\(p\) is prime either; evaluate the following Sage cell to verify this.
Certainly the computation above doesn’t always give primes (recall for instance the discussion at the end of
Subsection 7.5.2), but it’s not a bad source.
Implementing a program like this on normal computers is conceivable is because of a special test which applies just to numbers of the form \(2^p-1\text{.}\)
Algorithm 12.1.9. Lucas-Lehmer test.
Let \(x_0=4\) and let \(p\) be prime (greater than \(2\)). To test whether \(2^p-1\) is prime, create the list of numbers
\begin{equation*}
x_{n+1}=\text{residue of }x_n^2-2\text{ modulo }2^p-1
\end{equation*}
Do this \(p-2\) times; if the result \(x_{p-2}\) is divisible by \(2^p-1\) (i.e., is zero modulo \(2^p-1\)), then \(2^p-1\) is in fact prime.
Example 12.1.10.
With \(p=5\) and \(2^p-1=31\text{,}\) we would start with \(x_0=4\text{;}\) doing it \(5-2=3\) times gives:
\(4^2-2=14\) modulo \(31\) is \(14\)
\(14^2-2=194\) modulo \(31\) is \(8\)
\(8^2-2=62\) modulo \(31\) is \(0\)
And of course \(31\) is indeed prime.
You can try the test, naively implemented in Sage, in the following cell.
Subsection 12.1.4 Primes from Mersenne numbers
We can prove the lesser result that Mersenne numbers are coprime, which (just as with the Fermat numbers) can give us a lot of interesting prime factors.
Proposition 12.1.11. Mersenne numbers are coprime.
Mersenne numbers \(2^p-1\) and \(2^q-1\) with coprime exponents are themselves coprime.
Proof.
By way of contradiction, let \(d>1\) be the gcd of the two numbers \(2^p-1\) and \(2^q-1\text{.}\) Let’s investigate the order of \(2\neq 1\) in \(U_{d}\text{.}\) (Before reading more, think about why \(2\) is even in this group.)
By definition of divisibility,
\begin{equation*}
2^p\equiv 1\text{ (mod }d)\text{ and }2^q\equiv 1\text{ (mod }d)
\end{equation*}
By group theory (use
Theorem 8.3.12) we know that
\(2^k\equiv 1\) means that
\(k\) is a multiple of the order
\(|2|\) of the element
\(2\text{.}\) Thus
\(p\) and
\(q\) both are multiples of
\(|2|\text{.}\)
Since \(p\) and \(q\) are coprime, though, the only possibility for \(|2|\) is that \(|2|=1\text{.}\) This is a contradiction, so our assumption that \(d>1\) was wrong.
See the witty article
[E.7.24] for an argument that we shouldn’t expect many!
www-history.mcs.st-andrews.ac.uk/Biographies/Pascal.html
www-history.mcs.st-andrews.ac.uk/Biographies/Fermat.html
www-history.mcs.st-andrews.ac.uk/Biographies/Descartes.html
www-history.mcs.st-andrews.ac.uk/Biographies/Roberval.html
For more on the precise nature of his suggestion, its provenance, and the ‘rule’ by which he seems to have tried to decide which of these numbers should be considered, see Stillman Drake’s article
The rule behind ‘Mersenne’s numbers’ in Physis Volume 13, Number 4, and
Vittorio Boria’s dissertation, Marin Mersenne: Educator of scientists (available at
https://dra.american.edu
).
www.mersenne.org/primes/press/M82589933.html
www.youtube.com/watch?v=tlpYjrbujG0
arstechnica.com/gadgets/2016/01/intel-skylake-bug-causes-pcs-to-freeze-during-complex-workloads/
www.youtube.com/watch?v=09JslnY7W_k