Section12.1Finding More Primes

As we have seen, it is not terribly hard to find lots of small primes easily – by using the Sieve of Eratosthenes, or by making 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. This is despite the fact that they seem to follow very nice rules on average, which we will explore later.

Subsection12.1.1Fermat Primes

Recall 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.

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, whose proof is just multiplication.

Example12.1.2

For instance, \(2^6-1=63\) factors as \[2^{3\cdot 2}-1=(2^3+1)(2^3-1)\] which corresponds to the factorization \(9\cdot 7\). Similarly, \(2^{12}-1=4095\) factors as \[2^{3\cdot 4}-1=(2^3+1)(2^9-2^6+2^3-1)\] which corresponds to the factorization \(9\cdot 455\).

Subsection12.1.3Mersenne Primes

Another early attempt at this 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, and their friends) but also wrote major theological and music theoretical treatises of his own. He suggested that one try searching for primes of the form \(2^p-1\), where \(p\) is itself prime.

Certainly this isn't always giving us primes, but it's not bad. You can help the world search for more such 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 was found in January 2013! The largest known such primes are VERY large - this one has over seventeen 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 are not common enough to use for serious applications, but nonetheless help us investigate ideas about primes.

Subsubsection12.1.3.1Another special test

The reason this is conceivable is because of a special test, known as the Lucas-Lehmer test, which applies just to numbers \(2^p-1\). One start with \(x_0=4\), and then keeps feeding \(x\) into the loop \[x_{n+1}=\text{residue of }x_n^2-2\text{ modulo }2^p-1\; ;\] if the number you get after doing this \(p-2\) times is still divisible by \(2^p-1\) (i.e., zero), then \(2^p-1\) is in fact prime.

With \(p=5\) and \(2^p-1=31\), we would start with \(x_0=4\); doing it \(5-2=3\) times gives:

  1. \(4^2-2=14\) modulo \(31\) is \(14\)
  2. \(14^2-2=194\) modulo \(31\) is \(8\)
  3. \(8^2-2\) modulo \(31\) is \(0\)
And of course \(31\) is indeed prime.

Subsection12.1.4Primes from Mersenne Numbers

Again, proving this is slightly beyond our capabilities right now. But also once again, we can prove the lesser result that Mersenne numbers are coprime.

See this video featuring Dr. Holly Krieger, by Numberphile for an interesting take on this; all Mersenne numbers after \(2^6-1\) (even the ones where \(p\) is not prime!) have a new prime divisor.