1.14: Fermat Primes and Mersenne Primes
- Page ID
- 83348
Finding large primes and proving that they are indeed prime is not easy. For a long time, people have looked for formulas for producing prime numbers, with varying degrees of success. In this chapter we’ll learn about related questions and answers contributed by many people over the past several centuries—and even in the current one.
Let \(f(n) = n^2 - n + 41\), where \(n\) is a postive integer. As we plug in \(1,2,\dots\), the first few numbers we get the sequence \[41,43, 47, 53, 61, ...,\nonumber \] which seems to be producing a lot of prime numbers. In fact, the first forty terms are all prime, up to and including \(40^2-40+41 = 1601\), so if we were to make a hasty generalization, we might suspect that \(f(n)\) will always be prime, and we have found a simple formula for generating prime numbers.
This is false, however—observe what happens if we let \(n=41\): \[f(41)=41^2-41+41 = 41\cdot 41.\nonumber \] Similar results occur whenever \(n\) is a multiple of \(41\), so unfortunately \(f\) does not always produce prime numbers.
The functions \(f(n)\) and the similar polynomial \(n^2+n+41\), both examples of polynomials that produce several prime numbers, were studied by the great mathematicians Leonhard Euler (1707–1783) and Adrien-Marie Legendre (1752–1833). It was shown by Christian Goldbach (1690–1764) in 1752 that no polynomial with integer coefficients can generate only prime numbers, so such polynomials as \(f(n)\) cannot be used to consistently generate primes.
The function \(g(n)=6n+5\) clearly does not always produce primes, by Goldbach’s proof. It is also easy to see that \(g(6)=35=5\cdot 7\), and \(5\) divides \(g(n)\) whenever \(n\) is a multiple of 5.
However, Exercise 1.11.2 indicates that every prime number other than 2 or 3 has the form \(6n+1\) or \(6n+5\). Since there are infinitely many primes, either \(g(n)=6n+5\) or \(h(n)=6n+1\) (or both) must produce a prime number for infinitely many \(n\). Exercise \(\PageIndex{2}\) leads you through showing that this is true for \(g(n)\).
In fact, Johann Lejeune Dirichlet (1805–1859) showed in 1837 that whenever \(a\) and \(b\) are relatively prime, the function \(f(n)=an+b\) produces a prime number for infinitely many values of \(n\). In 2004, Ben Green and Terrence Tao announced a proof that for any positive length \(k\), there exist coefficients \(a\) and \(b\) such that \(f(n)=an+b\) will produce at least \(k\) primes using consecutive values of \(n\). (For example, \(g(0)=5, g(1)=11, g(2)=17, g(3)=23, g(4)=29\), so \(6n+5\) already produces primes for five consecutive values of \(n\).)
Though functions like \(n^2-n+41\) or \(6n+5\) cannot always produce primes, large numbers of primes (and sometimes infinitely many) do have this form, so one way to find primes, and perhaps very large primes, is to look at numbers that have some special form. For example, several of the smallest primes, like \(3\), \(5\), \(7\), \(17\), \(31\) are all either one unit less than or one unit more than a power of 2. With that in mind, the rest of this chapter will look at the following.
For which values of \(a\) and \(n\) might \[a^{n}+1\quad\text{or}\quad a^n-1\nonumber\] be a prime number?
It is easy to rule out some values of \(a\) and \(n\). For example we have the following.
Let \(a>1\) and \(n>1\). The following are true.
- If \(a^n-1\) is prime, then \(a=2\) and \(n\) is prime.
- If \(a^n+1\) is prime, then \(a\) is even and \(n=2^k\) for some \(k \ge 1\).
Proof of 1
We know from Exercise 1.3.8 that \[\label{eq12-1ast} a^n-1=(a-1)(a^{n-1}+\dotsb+a+1).\] If \(a>2\) and \(n>1\), then \(a-1>1\) and \(a^{n-1}+\dotsb+a+1>a+1>3\) so both factors in equation \(\eqref{eq12-1ast}\) are greater than 1 and thus \(a^n-1\) is not prime. Hence if \(a^n-1\) is prime we must have \(a=2\). Suppose this is the case, i.e., that \(2^n-1\) is prime. We claim that \(n\) is prime. If not, then \(n=st\) for integers \(s\) and \(t\) such that \(1<s<n\) and \(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\), forcing \(s=1\), a contradiction. Hence \(n\) must be prime, as claimed.
Proof of 2
Suppose first that \(n\) is odd. Replacing \(a\) by \(-a\) in equation \(\eqref{eq12-1ast}\), we get \[(-a)^n-1=(-a-1)\left((-a)^{n-1}+(-a)^{n-2}+\dotsb+(-a)+1\right)\nonumber \] 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. Substituting these values 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\), then \(a^n + 1> a+1\), and the equation above shows that when \(n\) is odd and \(a>1\), the number \(a^n+1\) is not prime, since \(a+1\) is a divisor strictly between \(1\) and \(a^n+1\). Therefore, if \(a^n+1\) is supposed to be prime, it must be the case that \(n\) is even.
Suppose now that \(n\) is even, and express it as \(n=2^st\), where \(t\) is odd (so \(s \geq 1\)). If \(a^n+1\) is prime, then \((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\). Since \(t\) is odd, we must have \(t=1\) and so \(n=2^s\).
Finally, note that since \(n\) is positive, \(a\) and \(a^n\) have the same parity, so \(a^n+1\) is odd if and only if \(a\) is even. The number 2 (the only even prime) is too small to be written as \(a^n+1\) for any \(a>1\) and \(n>1\), so if \(a^n+1\) is prime, then \(a\) is even and \(n\) is a power of 2, as claimed.
Number theorists have studied the prime numbers satisfying the conclusions in Theorem \(\PageIndex{1}\). We remember two in particular, namely Pierre de Fermat (1607–1665) and Marin Mersenne (1588–1648), through names given to these numbers.
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. 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.
As Fermat studied the numbers now named after him, he conjectured that all Fermat numbers are prime. Indeed, 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 in a reasonable amount of time. However, it is now 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 \(18233954\) (the largest one known as of a recent revision of this text)\(^{1}\). It is now conjectured that \(F_n\) is composite for all \(n\ge 5\). So Fermat’s original thought that \(F_n\) is prime for \(n\ge 0\) seems to be pretty far from reality.
Mersenne, a friend of mathematician and philosopher René Descartes, studied the Mersenne numbers and attempted to make a list of Mersenne primes with exponents up to 257, though the list contained some errors. To see some small Mersenne numbers, look at the numbers \(M_2=2^2-1 = 3\) and \(M_3=2^3-1 = 7\), which are both Mersenne primes, and at \(M_4=2^4-1=15\), which is a Mersenne number but not a prime (this should not be suprising in light of Theorem \(\PageIndex{1}\), since the exponent 4 is not prime). We pause here to reiterate this idea.
If \(M_n\) is prime, then \(n\) is prime.
Proof
This is immediate from Theorem \(\PageIndex{1}\)(1).
You might wonder whether the converse of this Lemma is true—whether \(M_p=2^p-1\) is prime whenever \(p\) is prime. The answer is no; the Mersenne number \(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 \(51\) Mersenne primes have been found. It is known that \(2^p-1\) is prime if \(p\) is one of the following 51 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, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933.
The largest Mersenne prime currently known, \(M_{82589933}=2^{82589933}-1\), was found on December 7, 2018. The decimal representation of this number has \(24,862,048\) digits (about one and one-half million digits more than in the representation of \(M_{77232917}\)). It was found by a computer volunteered by Patrick Laroche as a part of the Great Internet Mersenne Prime Search (GIMPS); see www.mersenne.org for more about this. This prime could be the 51st Mersenne prime (in order of size), but we will only know this for sure when GIMPS completes testing all prime exponents between 43112609 and 82589933. Later we show the connection between Mersenne primes and a special class of numbers called perfect numbers.
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.
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\).
[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.]
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.
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^{p/2}\) steps. This is MUCH larger than \(p\) in general.
This chapter has introduced Fermat and Mersenne numbers and primes and some of what we know about them. Hopefully you have noticed from the names and dates mentioned here that it has taken the work of many people over a long time to find out what we know now. Hopefully you have also gotten a sense that this work is not over—there is much more to learn! Some basic unsolved questions are here.
- Are there infinitely many primes of the form \(2^{2^n}+1\) (i.e, Fermat primes)?
- Are there infinitely many primes of the form \(2^n-1\) (i.e., Mersenne primes)?
When will we have answers? Who will provide them? Will you be part of that work?
Exercises
Show that if \[f(x) = a_px^p + a_{p-1}x^{p-1}+\cdots+a_2x^2+a_1x+a_0,\nonumber \] where \(a_0,\dots, a_p\) are all integers, with \(a_p \neq 0\) and \(p\geq 1\) and \(a_0>1\), then there exists a value of \(x\) such that \(f(x)\) is guaranteed not to be prime. (Give an example of such a value.)
In this exercise, we will show that \(g(n)=6n+5\) will produce a prime number for infinitely many values of \(n\).
- Show that other than 2 or 3, every prime number has the form \(6n+1\) or \(6n+5\).
(Compare this to Exercise 1.11.2.) - Show that multiplying any two numbers of the form \(6n+1\) creates another number of the form \(6n+1\).
- Show that multiplying two numbers of the form \(6n+5\) creates a number of the form \(6n+1\).
- Show that there are infinitely many primes of the form \(6n+5\). (Hint: imitate Euclid’s proof in Theorem 1.11.1, showing that if \(q_1,q_2,\ldots ,q_k\) are all primes of the form \(6n+5\), then \(q_1q_2\cdots q_k+4\) or \(5q_1q_2\cdots q_k+4\) must have a prime divisor of the form \(6n+5\).
Use a computer to factor \(F_5\), describing any steps and tools you use.
Prove that if \(m,n\) are integers with \(m<n\), then \(F_m \mid (F_n - 2)\).
(Hint: Recall how to factor a difference of squares.)
- Use the previous exercise to show that \(\gcd(F_m,F_n) = 1\) whenever \(m \neq n\).
- Explain why part (a) gives a new proof that there are infinitely many prime numbers.
- Use mathematical induction to show that \[F_n = (F_{n-1}-1)^2 + 1\nonumber \] for all \(n \geq 2\).
- Use mathematical induction and part (a) to show that other than \(F_0\) and \(F_1\), all Fermat numbers have 7 as their last digit.
Find all integers, if any, that are both a Mersenne prime and a Fermat prime. Justify your answer.
Determine which Mersenne numbers \(M_n\) are prime when \(2\le n\le 12\). You may use a computer or computer algebra system for this exercise, though in your answer you should describe all steps and tools you use.
Show using the Lucas-Lehmer test that \(M_7=127\) is prime.
Footnotes
[1] This value was announced in October 2020 by user ryanp at https://www.mersenneforum.org/showth...=15449&page=28.