Mersenne prime
In mathematics, a Mersenne prime is a prime number that is one less than a power of two.
≈ 6 min read
Mersenne prime. encyclopegia.org, snapshot enwiki-001373929786. /a/mersenne-prime
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century.
If is a composite number then so is . Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form for some prime . The exponents that give Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, ... and the resulting Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ... .
Numbers of the form without the primality requirement may be called Mersenne numbers. Sometimes, however, Mersenne numbers are defined to have the additional requirement that should be prime. The smallest composite Mersenne number with prime exponent is .
Mersenne primes were studied in antiquity because of their close connection to perfect numbers: the Euclid–Euler theorem asserts a one-to-one correspondence between even perfect numbers and Mersenne primes. Many of the largest known primes are Mersenne primes because Mersenne numbers are easier to check for primality. , 52 Mersenne primes are known.
The largest known prime number, , is a Mersenne prime. Since 1997, all newly found Mersenne primes have been discovered by the Great Internet Mersenne Prime Search, a distributed computing project.
In December 2020, a major milestone in the project was passed after all exponents below 100 million were checked at least once. &=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)\\ &=(2^b-1)\cdot \left(1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b}\right). \end{align} This rules out primality for Mersenne numbers with a composite exponent, such as . Though the above examples might suggest that is prime for all primes , this is not the case, and the smallest counterexample is the Mersenne number .
Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite or infinite.
The Lenstra–Pomerance–Wagstaff conjecture claims that there are infinitely many Mersenne primes and predicts their order of growth and frequency: For every number , there should on average be about e^\gamma\cdot\log_2(10) \approx 5.92 primes with decimal digits for which is prime. Here, is the Euler–Mascheroni constant.
It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed conjectures about prime numbers; for example, from the infinitude of Sophie Germain primes congruent to 3 (mod 4). For these primes , (which is also prime) will divide , for example, , , , , , , , and .
For these primes , is congruent to 7 mod 8, so 2 is a quadratic residue mod , and the multiplicative order of 2 mod must divide \frac{(2p+1)-1}{2} = p . Since is a prime, it must be or . However, it cannot be 1 since and has no prime factors, so it must be . Hence, divides and cannot be prime.
The first four Mersenne primes are , , and and because the first Mersenne prime starts at , all Mersenne primes are congruent to 3 (mod 4). Other than and , all other Mersenne numbers are also congruent to 3 (mod 4). Consequently, in the prime factorization of a Mersenne number ( ) there must be at least one prime factor congruent to 3 (mod 4).
The evidence at hand suggests that a randomly selected Mersenne number is much more likely to be prime than an arbitrary randomly selected odd integer of similar size. Nonetheless, prime values of appear to grow increasingly sparse as increases.
For example, eight of the first 11 primes give rise to a Mersenne prime (the correct terms on Mersenne's original list), while is prime for only 43 of the first two million prime numbers (up to 32452843). Since Mersenne numbers grow very rapidly, the search for Mersenne primes is a difficult task, even though there is a simple efficient test to determine whether a given Mersenne number is prime: the Lucas–Lehmer primality test (LLT), which makes it much easier to test the primality of Mersenne numbers than that of most other numbers of the same size.
The search for the largest known prime has somewhat of a cult following. Consequently, a large amount of computer power has been expended searching for new Mersenne primes, much of which is now done using distributed computing.
Arithmetic modulo a Mersenne number is particularly efficient on a binary computer, making them popular choices when a prime modulus is desired, such as the Park–Miller random number generator. To find a primitive polynomial of Mersenne number order requires knowing the factorization of that number, so Mersenne primes allow one to find primitive polynomials of very high order.
Such primitive trinomials are used in pseudorandom number generators with very large periods such as the Mersenne twister, generalized shift register and Lagged Fibonacci generators.
Eisenstein Mersenne primes
One may encounter cases where such a Mersenne prime is also an Eisenstein prime, being of the form and . In these cases, such numbers are called Eisenstein Mersenne primes. is an Eisenstein prime for the following : 2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153, 7541, 9049, 10453, 23743, 255361, 534827, 2237561, ...
The norms (that is, squares of absolute values) of these Eisenstein primes are rational primes: 7, 271, 2269, 176419, 129159847, 1162320517, ...
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373929786 under CC BY-SA 4.0; modifications have been made.