Definition12.1.1
We call numbers of the form \(F_n=2^{2^n}+1\) Fermat numbers.
Section12.1Finding More Primes¶ permalink
As we have seen, it is not terribly hard to find lots of small primes easily. One can use Sieve of Eratosthenes, or make numbers coprime to known primes and then factoring them.
The problem is that almost every effort to find lots of big ones has been stymied. Primes simply do not follow nice enough rules to find them easily. This is despite the fact that they seem to follow very nice rules on average, which we will explore in later chapters.
Subsection12.1.1Fermat primes¶ permalink
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\), \(17\), and \(257\).
However, in 1732 Euler proved that this is not true for \(n=5\):
Nobody knows if there are any more primes in this sequence. Even the prime factors seem to be quite large, though.
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\). Proving it is just a little beyond us right now, so we will not address it here (see Subsection 17.5.2, though).
Subsection12.1.2Primes from Fermat numbers
However, we can at least prove what seems obvious above – namely, that lots of primes come out of Fermat numbers. First, we need a lemma.
Lemma12.1.2
If \(\ell=jk\), and \(k\) is even, 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*}
Example12.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\). 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\).
Proposition12.1.4Fermat numbers are coprime
\(F_n=2^{2^n}+1\) and \(F_m=2^{2^m}+1\) are coprime if \(m\neq n\).
Subsection12.1.3Mersenne primes¶ permalink
Another early attempt at finding big primes was an idea of Marin Mersenne. Mersenne was a Minim monk who not only acted as a clearinghouse for scientific knowledge in early 17th century France (particularly between Pascal, Fermat, Descartes, Roberval, and their friends) but also wrote major theological and music theoretical treatises of his own.
Mersenne suggested that one try searching for primes of the form \(2^p-1\), where \(p\) is itself prime.
Definition12.1.5
In general, numbers of the form \(M_n=2^n-1\) are called Mersenne numbers. If they are prime, they are called Mersenne primes.
Certainly this doesn't always give primes, but it's not bad. You can help the world search for more Mersenne primes if you leave your personal computer on and connected to the Internet, via the Great Internet Mersenne Prime Search (GIMPS). Random computers in labs at the University of Central Missouri and UCLA have found some of the largest known primes this way.
The most recent one (as of this writing) was found in January 2016! The largest known such primes are very large; this one has over twenty-two million digits. GIMPS even won a monetary prize for finding these huge ones; they shared it with many of the people who made it possible.
These primes are far too large and are not common enough to use for serious applications, but nonetheless help us investigate ideas about primes. Interestingly, although it is not necessarily an application one might think of, searching for them can also help more mundane hardware testing. A good example of this is that computing the GIMPS program uncovered a bug in a major Intel chip. Number theory can push our hardware (and software!) beyond our imagination.
The reason implementing something like this is conceivable is because of a special test which applies just to numbers \(2^p-1\).
Algorithm12.1.6Lucas-Lehmer test
Let \(x_0=4\) and let \(p\) be prime. 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 is divisible by \(2^p-1\) (i.e., is zero modulo \(2^p-1\)), then \(2^p-1\) is in fact prime.
Example12.1.7
With \(p=5\) and \(2^p-1=31\), we would start with \(x_0=4\); 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.
Proving this is slightly beyond our capabilities right now.
Subsection12.1.4Primes from Mersenne numbers
Although we didn't prove the test, 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.
Proposition12.1.8Mersenne numbers are coprime
Mersenne numbers \(2^p-1\) and \(2^q-1\) with coprime exponents are themselves coprime.
See this video featuring Holly Krieger, by Numberphile for an interesting take on this. Namely, all Mersenne numbers after \(2^6-1\) (even the ones where \(p\) is not prime!) have a new prime divisor.