NTIC Finding More Primes

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 [C.5.5] for an engaging take on the story.) Evaluate the following cell, which quickly produces numbers a bit long for print!

xxxxxxxxxx
 
for n in [0..7]:
    pretty_print(html("If $n=%s$, then $2^{2^n}+1=2^{2^%s}+1=%s$ factors as $%s$"%(n,n,2^(2^n)+1,factor(2^(2^n)+1))))

🔗

For example,

$\begin{equation*} 2^{2^7}+1 = 59649589127497217\cdot 5704689200685129054721\text{.} \end{equation*}$

🔗

Nobody knows if there are any more primes¹See the witty article [C.7.24] for an argument that we shouldn't expect many! in the sequence

$F_n$ past

$n=4\text{,}$ but 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{.}$

🔗

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.

Multiply and/or apply a little induction. (See Exercise 12.7.1.)

🔗

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.

🔗

Remark 12.1.5.

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

xxxxxxxxxx
 
for p in prime_range(100):
    pretty_print(html("If $p=%s$, then $2^p-1=2^{%s}-1=%s$ factors as $%s$"%(p,p,2^p-1,factor(2^p-1))))

🔗

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. 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 December 2018! The largest known such primes are very large; this one has nearly twenty-five million digits, and the folks at Numberphile made a very amusing video unwrapping a book containing a previous record holder of ‘only’ twenty-two million digits. GIMPS even won a monetary prize for finding these huge primes; 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 most serious applications²Though see United States patent 6307935, which explicitly uses them to directly encrypt onto a special elliptic curve., but nonetheless they help us investigate ideas about primes. A less obvious but interesting application is that searching for very large primes 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.

🔗

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.7. Lucas-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 $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.8.

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.

xxxxxxxxxx
 
@interact
def _(p=(71,prime_range(100))):
    test = 4
    num = 2^p-1
    for i in range(p-2):
        test=(test^2-2)%num
    pretty_print(html("The test says "+str(bool(test==0))))
    pretty_print(html("And in fact $2^{%s}-1=%s$ primality is "%(p,num)+str(is_prime(num))))

🔗

Proving Algorithm 12.1.7 is slightly beyond our capabilities in this text.

🔗

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.9. 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 this linked 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.