Mersenne prime

Mersenne prime. A Mersenne prime is a prime number that is one less than a power of two, having the form 2^p − 1, where the exponent p itself must also be prime. These numbers are named after the 17th-century French Minim friar Marin Mersenne, who compiled an early list of such numbers. Their special form makes them central to the study of number theory and they are intimately connected to the search for perfect numbers, as proven by Euclid and later by Leonhard Euler.

Definition and basic properties

A number of the form M_p = 2^p − 1 is defined as a Mersenne number. For it to be prime, the exponent p must itself be a prime number, a necessary but not sufficient condition. This connection was formally studied by Édouard Lucas in the 19th century. The binary representation of a Mersenne prime is simply a string of p ones, a property leveraged in computer algorithms. Furthermore, every Mersenne prime corresponds to an even perfect number through the theorem established by Euclid and completed by Leonhard Euler, a foundational result in number theory.

History and discovery

The study of these numbers dates to antiquity, with Euclid's work in Elements linking them to perfect numbers. Marin Mersenne made his famous assertion in his 1644 work Cogitata Physico-Mathematica, claiming M_p was prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257. This list contained errors, as later work by Leonhard Euler, Chebyshev, and others revealed. The 19th century saw major progress with Édouard Lucas, who developed a primality test, used to prove M₁₂₇ prime, a record held until the computer age. The modern search is dominated by the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project founded by George Woltman.

Mathematical significance

Mersenne primes are profoundly significant in number theory. Their direct generation of perfect numbers via Euclid–Euler theorem provides a direct link to a classical problem studied by Pythagoras and Nicomachus. They are also pivotal in the field of pseudoprimes and primality testing, with the Lucas–Lehmer primality test offering a remarkably efficient algorithm. The search for these primes has driven advancements in computational number theory and distributed computing, exemplified by projects like GIMPS. Their properties are also explored in algebraic number theory, particularly in relation to finite fields and pseudorandom number generators.

Primality testing and algorithms

The primary method for testing Mersenne numbers is the Lucas–Lehmer primality test, a deterministic algorithm developed from the work of Édouard Lucas and refined by Derrick Henry Lehmer. This test is exceptionally efficient for numbers of this special form, requiring only modular arithmetic. Its implementation is central to software like the GIMPS client, which uses the LLR and Prime95 programs. Before applying this test, potential exponents are typically sieved using algorithms like the Sieve of Eratosthenes to eliminate candidates with small factors. The entire computational effort is coordinated via the Internet and has led to records verified by authorities like the Electronic Frontier Foundation.

List of known Mersenne primes

As of 2023, there are 51 known examples, all discovered through extensive computation. The first four—3, 7, 31, 127—were known in antiquity. The fifth, M₁₃ (8191), was found in the Middle Ages by anonymous scholars. The largest known prime number is almost always a Mersenne prime; the current record is M_82589933, discovered in 2018 by Patrick Laroche as a participant in GIMPS. Notable discoveries include M_43112609, which won a prize from the Electronic Frontier Foundation. The complete list is maintained by the project and recognized by the On-Line Encyclopedia of Integer Sequences (OEIS).

Category:Integer sequences Category:Prime numbers Category:Classes of prime numbers