1.12: Fermat Primes and Mersenne Primes

Finding large primes and proving that they are indeed prime is not easy. One way to find large primes is to look at numbers that have some special form, for example, numbers of the form \(a^n+1\) or \(a^n-1\). It is easy to rule out some values of \(a\) and \(n\). For example we have:

Theorem \(\PageIndex{1}\)

Let \(a>1\) and \(n>1\). Then

1. \(a^n-1\) is prime \(\Rightarrow a=2\) and \(n\) is prime
2. \(a^n+1\) is prime \(\Rightarrow a\) is even and \(n=2^k\) for some \(k \ge 1\).

Proof

Proof of (1). We know from Exercise 2.5, that \[\label{eq:1}a^n -1=(a-1)(a^{n-1}+\cdots +a+1)\] Note that if \(a>2\) and \(n>1\) then \(a-1>1\) and \(a^{n-1}+\dotsb+a+1>a+1>3\) so both factors in \(\eqref{eq:1}\) are \(>1\) and \(a^n-1\) is not prime. Hence if \(a^n-1\) is prime we must have \(a=2\). Now suppose \(2^n-1\) is prime. We claim that \(n\) is prime. If not \(n=st\) where \(1<s<n\), \(1<t<n\). Then \[2^n-1=2^{st}- 1=(2^s)^t-1\nonumber \] is prime. But we just showed that if \(a^n-1\) is prime we must have \(a=2\). So we must have \(2^s=2\). Hence \(s=1\), \(t=n\). So \(n\) is not composite. Hence \(n\) must be prime. This proves (1).

Proof of (2). From \(\eqref{eq:1}\) we have \[ a^n-1=(a-1)(a^{n-1}+a^{n-2}+\dotsb+a+1). \nonumber\] Replace \(a\) by \(-a\) in \(\eqref{eq:1}\) and we get \[\label{eq:2}(-a)^n-1=(-a-1)\left((-a)^{n-1}+(-a)^{n-2}+\dotsb+(-a)+1\right) \] Since \(n\) is odd, \(n-1\) is even, \(n-2\) is odd, \(\dotsc\), etc., we have \((-a)^n=-a^n,(-a)^{n-1}=a^{n-1},(-a)^{n-2}=-a^{n-2},\dotsc\), etc. So \(\eqref{eq:2}\) yields \[-(a^n+1)=-(a+1)\left(a^{n-1}-a^{n-2}+\dotsb+-a+1\right).\nonumber\] Multiplying both sides by \(-1\) we get \[(a^n+1)=(a+1)(a^{n-1}-a^{n-2}+\dotsb-a+1)\nonumber\] when \(n\) is odd. If \(n\ge 2\) we have \(1<a+1<a^n+1\). This shows that if \(n\) is odd and \(a>1\), \(a^n+1\) is not prime. Suppose \(n=2^st\) where \(t\) is odd. Then if \(a^n+1\) is prime we have \((a^{2^s})^t+1\) is prime. But by what we just showed this cannot be prime if \(t\) is odd and \(t\ge 2\). So we must have \(t=1\) and \(n=2^s\). Also \(a^n+1\) prime implies that \(a\) is even since if \(a\) is odd so is \(a^n\). Then \(a^n+1\) would be even. The only even prime is \(2\). But since we assume \(a>1\) we have \(a\ge 2\) so \(a^n+1\ge 3\).

Definition \(\PageIndex{1}\)

A number of the form \(M_n=2^n-1\), \(n\ge 2\), is said to be a Mersenne number. If \(M_n\) is prime, it is called a Mersenne prime. A number of the form \(F_n=2^{(2^n)}+1\), \(n\ge 0\), is called a Fermat number. If \(F_n\) is prime, it is called a Fermat prime.

One may prove that \(F_0=3\), \(F_1=5\), \(F_2=17\), \(F_3=257\) and \(F_4=65537\) are primes. As \(n\) increases the numbers \(F_n=2^{(2^n)}+1\) increase in size very rapidly, and are not easy to check for primality. It is known that \(F_n\) is composite for many values of \(n\ge 5\). This includes all \(n\) such that \(5\le n\le 30\) and a large number of other values of \(n\) including \(382447\) (the largest one I know of). It is now conjectured that \(F_n\) is composite for \(n\ge 5\). So Fermat’s original thought that \(F_n\) is prime for \(n\ge 0\) seems to be pretty far from reality.

Exercise \(\PageIndex{1}\)

Use Maple to factor \(F_5\). [Go to any campus computer lab. Click or double-click on the Maple icon—or ask the lab assistant where it is located. When the window comes up, type at the prompt \(>\) the following:

     > ifactor(2^32 + 1);

Hit the return key and you will get the answer.]

\(M_3=2^3-1 = 7\) is a Mersenne prime and \(M_4=2^4-1=15\) is a Mersenne number which is not a prime. At first it was thought that \(M_p=2^p-1\) is prime whenever \(p\) is prime. But \(M_{11}=2^{11}-1=2047=23\cdot89\) is not prime.

Over the years people have continued to work on the problem of determining for which primes \(p\), \(M_p=2^p-1\) is prime. To date \(39\) Mersenne primes have been found. It is known that \(2^p-1\) is prime if \(p\) is one of the following 39 primes 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917.

The largest one, \(M_{13466917}=2^{13466917}-1\), was found on November 14, 2001. The decimal representation of this number has \(4,053,946\) digits. It was found by the team of Michael Cameron, George Woltman, Scott Kurowski et al, as a part of the Great Internet Mersenne Prime Search (GIMPS), see Chris Caldwell’s page for more about this. This prime could be the 39th Mersenne prime (in order of size), but we will only know this for sure when GIMPS completes testing all exponents below this one.You can find the link to Chris Caldwell’s page on the class syllabus on my homepage. Later we show the connection between Mersenne primes and perfect numbers.

Lemma \(\PageIndex{1}\)

If \(M_n\) is prime, then \(n\) is prime.

Proof

This is immediate from Theorem \(\PageIndex{1}\) (1).

The most basic question about Mersenne primes is: Are there infinitely many Mersenne primes?

Exercise \(\PageIndex{2}\)

Determine which Mersenne numbers \(M_n\) are prime when \(2\le n\le 12\). You may use Maple for this exercise. The Maple command for determining whether or not an integer n is prime is

 isprime(n);

The following primality test for Mersenne numbers makes it easier to check whether or not \(M_p\) is prime when \(p\) is a large prime.

Theorem \(\PageIndex{2}\): The Lucas-Lehmer Mersenne Prime Test

(The Lucas-Lehmer Mersenne Prime Test). Let \(p\) be an odd prime. Define the sequence \[r_1,r_2,r_3,\dotsc,r_{p-1}\nonumber\] by the rules \[r_1=4\nonumber\] and for \(k\ge 2\), \[r_k= (r_{k-1}^2-2) \bmod M_p.\nonumber\] Then \(M_p\) is prime if and only if \(r_{p-1}=0\).

Proof

The proof of this is not easy. One place to find a proof is the book “A Selection of Problems in the Theory of Numbers” by W. Sierpinski, Pergamon Press, 1964.

Example \(\PageIndex{1}\)

Let \(p=5\). Then \(M_p=M_5=31\). \[\begin{aligned} r_1 &=4 \\ r_2 &=(4^2-2) \bmod 31=14\bmod 31=14 \\ r_3 &=(14^2-2) \bmod 31=194\bmod 31=8 \\ r_4 &=(8^2-2) \bmod 31=62\bmod 31=0.\end{aligned}\] Hence by the Lucas-Lehmer test, \(M_5=31\) is prime.

Exercise \(\PageIndex{3}\)

Show using the Lucas-Lehmer test that \(M_7=127\) is prime.

Remark \(\PageIndex{1}\)

Note that the Lucas-Lehmer test for \(M_p=2^p-1\) takes only \(p-1\) steps. On the other hand, if one attempts to prove \(M_p\) prime by testing all primes \(\le\sqrt{M_p}\) one must consider about \(2^{\frac p2}\) steps. This is MUCH larger than \(p\) in general.