TAOCP 4.5.4 Exercise 16

A _Mersenne number_ is a number of the form $M_p = 2^p - 1,$ where $p$ is a positive integer.

taocpmathematicsalgorithmsvolume-2math-research

Section 4.5.4: Factoring into Primes

Exercise 16. [M50] Are there infinitely many Mersenne primes?

Verified: yes
Solve time: 4m51s

Setup

A Mersenne number is a number of the form

$M_p = 2^p - 1,$

where $p$ is a positive integer. A Mersenne prime is a Mersenne number that is prime.

We are asked to determine whether there exist infinitely many Mersenne primes, that is, whether the set

${p \in \mathbb{Z}^+ : 2^p - 1 \text{ is prime}}$

is infinite.

No specific assumptions about $p$ are given, except that $p$ must be prime in order for $2^p - 1$ to be potentially prime (since if $p$ is composite, $2^p - 1$ is always composite by the factorization

$2^{ab} - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 1) \text{ for integers } a,b > 1).$

Thus, the exercise reduces to asking whether there are infinitely many primes $p$ such that $2^p - 1$ is prime.

Solution

Currently, it is unknown whether there are infinitely many Mersenne primes. The following facts are relevant:

  1. If $p$ is composite, then $2^p - 1$ is composite by the factorization above. Hence only prime $p$ can yield a Mersenne prime.
  2. If $p$ is prime, $2^p - 1$ may be prime or composite. There is no known formula that guarantees the primality of $2^p - 1$ for infinitely many primes $p$.
  3. The largest known primes are often Mersenne primes because of the Lucas–Lehmer primality test, which is efficient for numbers of the form $2^p - 1$.

As of now, the list of known Mersenne primes grows slowly. More than 50 Mersenne primes have been discovered, but there is no proof that the process continues indefinitely.

Consequently, the question of whether there are infinitely many Mersenne primes is an open problem in number theory.

Therefore, the answer is that the infinitude of Mersenne primes has not been established. No argument from first principles or existing theorems confirms it, although extensive computational evidence suggests they may be arbitrarily large.

Verification

  1. Suppose $2^p - 1$ is prime. Then $p$ must be prime. This has been verified via the factorization formula $2^{ab} - 1$.
  2. All known Mersenne primes correspond to prime exponents. For instance, $2^2 - 1 = 3$, $2^3 - 1 = 7$, $2^5 - 1 = 31$, $2^7 - 1 = 127$, and so on.
  3. There is no contradiction in stating that infinitude is unknown: no proof has been found showing that the sequence of Mersenne primes either terminates or continues indefinitely. This aligns with current literature in number theory.

Notes

  • The Lucas–Lehmer test provides an effective method for verifying the primality of $2^p - 1$ for known prime exponents $p$.
  • If a proof of infinitude were found, it would resolve a major open problem in number theory.
  • Heuristics and statistical models suggest that Mersenne primes become rarer as $p$ increases, but this is not a proof of finiteness.

This completes the solution.

∎

$\boxed{\text{Unknown; open problem in number theory}}$