Mersenne conjectures

Last updated February 28, 2024

In mathematics, the Mersenne conjectures concern the characterization of a kind of prime numbers called Mersenne primes, meaning prime numbers that are a power of two minus one.

Original Mersenne conjecture

The original, called Mersenne's conjecture, was a statement by Marin Mersenne in his Cogitata Physico-Mathematica (1644; see e.g. Dickson 1919) that the numbers $2^{n}-1$ were prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and were composite for all other positive integers n ≤ 257. The first seven entries of his list ( $2^{n}-1$ for n = 2, 3, 5, 7, 13, 17, 19) had already been proven to be primes by trial division before Mersenne's time;^[1] only the last four entries were new claims by Mersenne. Due to the size of those last numbers, Mersenne did not and could not test all of them, nor could his peers in the 17th century. It was eventually determined, after three centuries and the availability of new techniques such as the Lucas–Lehmer test, that Mersenne's conjecture contained five errors, namely two entries are composite (those corresponding to the primes n = 67, 257) and three primes are missing (those corresponding to the primes n = 61, 89, 107). The correct list for n ≤ 257 is: n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

While Mersenne's original conjecture is false, it may have led to the New Mersenne conjecture.

New Mersenne conjecture

The New Mersenne conjecture or Bateman, Selfridge and Wagstaff conjecture (Bateman et al. 1989) states that for any odd natural number p, if any two of the following conditions hold, then so does the third:

p = 2^k ± 1 or p = 4^k ± 3 for some natural number k. ( OEIS: A122834 )
2^p − 1 is prime (a Mersenne prime). ( OEIS: A000043 )
(2^p + 1)/3 is prime (a Wagstaff prime). ( OEIS: A000978 )

If p is an odd composite number, then 2^p − 1 and (2^p + 1)/3 are both composite. Therefore it is only necessary to test primes to verify the truth of the conjecture.

Currently, there are nine known numbers for which all three conditions hold: 3, 5, 7, 13, 17, 19, 31, 61, 127 (sequence A107360 in the OEIS ). Bateman et al. expected that no number greater than 127 satisfies all three conditions, and showed that heuristically no greater number would even satisfy two conditions, which would make the New Mersenne Conjecture trivially true.

As of 2024^[update], all the Mersenne primes up to 2^57885161 − 1 are known, and for none of these does the third condition hold except for the ones just mentioned.^[2]^[3] Primes which satisfy at least one condition are

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 67, 79, 89, 101, 107, 127, 167, 191, 199, 257, 313, 347, 521, 607, 701, 1021, 1279, 1709, 2203, 2281, 2617, 3217, 3539, 4093, 4099, 4253, 4423, 5807, 8191, 9689, 9941, ... (sequence A120334 in the OEIS )

Note that the two primes for which the original Mersenne conjecture is false (67 and 257) satisfy the first condition of the new conjecture (67 = 2⁶ + 3, 257 = 2⁸ + 1), but not the other two. 89 and 107, which were missed by Mersenne, satisfy the second condition but not the other two. Mersenne may have thought that 2^p − 1 is prime only if p = 2^k ± 1 or p = 4^k ± 3 for some natural number k, but if he thought it was "if and only if" he would have included 61.

Status of new Mersenne conjecture for the first 100 primes
2^[4]	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229
233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349
353	359	367	373	379	383	389	397	401	409
419	421	431	433	439	443	449	457	461	463
467	479	487	491	499	503	509	521	523	541

Red: p is of the form 2ⁿ±1 or 4ⁿ±3	Cyan background: 2^p−1 is prime	Italics: (2^p+1)/3 is prime	Bold: p satisfies at least one condition

The New Mersenne conjecture can be thought of as an attempt to salvage the centuries-old Mersenne's conjecture, which is false. However, according to Robert D. Silverman, John Selfridge agreed that the New Mersenne conjecture is "obviously true" as it was chosen to fit the known data and counter-examples beyond those cases are exceedingly unlikely. It may be regarded more as a curious observation than as an open question in need of proving.

Prime Pages shows that the New Mersenne conjecture is true for all integers less than or equal to 30402457^[2] by systematically listing all primes for which it is already known that one of the conditions holds.

Lenstra–Pomerance–Wagstaff conjecture

Lenstra, Pomerance, and Wagstaff have conjectured that there are infinitely many Mersenne primes, and, more precisely, that the number of Mersenne primes less than x is asymptotically approximated by

e^{\gamma }\cdot \log _{2}\log _{2}(x),

^[5]

where γ is the Euler–Mascheroni constant. In other words, the number of Mersenne primes with exponent p less than y is asymptotically

e^{\gamma }\cdot \log _{2}(y).

^[5]

This means that there should on average be about $e^{\gamma }\cdot \log _{2}(10)$ ≈ 5.92 primes p of a given number of decimal digits such that $M_{p}$ is prime. The conjecture is fairly accurate for the first 40 Mersenne primes, but between 2^20,000,000 and 2^85,000,000 there are at least 12,^[6] rather than the expected number which is around 3.7.

More generally, the number of primes p ≤ y such that ${\frac {a^{p}-b^{p}}{a-b}}$ is prime (where a, b are coprime integers, a > 1, −a < b < a, a and b are not both perfect r-th powers for any natural number r > 1, and −4ab is not a perfect fourth power) is asymptotically

(e^{\gamma }+m\cdot \log _{e}(2))\cdot \log _{a}(y).

where m is the largest nonnegative integer such that a and −b are both perfect 2^m-th powers. The case of Mersenne primes is one case of (a, b) = (2, 1).

Related Research Articles

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation:

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial:$

In mathematics, the gamma function is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers except the non-positive integers. For every positive integer $n$ ,

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 $M n = 2 n - 1$ for some integer $n$ . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If $n$ is a composite number then so is $2 n - 1$ . Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form $M p = 2 p - 1$ for some prime $p$ .

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is a perfect number.

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

11 (eleven) is the natural number following 10 and preceding 12. It is the first repdigit. In English, it is the smallest positive integer whose name has three syllables.

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

In recreational mathematics, a repdigit or sometimes monodigit is a natural number composed of repeated instances of the same digit in a positional number system. The word is a portmanteau of "repeated" and "digit". Examples are 11, 666, 4444, and 999999. All repdigits are palindromic numbers and are multiples of repunits. Other well-known repdigits include the repunit primes and in particular the Mersenne primes.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

127 is the natural number following 126 and preceding 128. It is also a prime number.

In mathematics, a double Mersenne number is a Mersenne number of the form

In number theory, a Wagstaff prime is a prime number of the form

John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

In number theory, a Pierpont prime is a prime number of the form

In number theory, Firoozbakht's conjecture is a conjecture about the distribution of prime numbers. It is named after the Iranian mathematician Farideh Firoozbakht who stated it first in 1982.

In number theory, Gillies' conjecture is a conjecture about the distribution of prime divisors of Mersenne numbers and was made by Donald B. Gillies in a 1964 paper in which he also announced the discovery of three new Mersenne primes. The conjecture is a specialization of the prime number theorem and is a refinement of conjectures due to I. J. Good and Daniel Shanks. The conjecture remains an open problem: several papers give empirical support, but it disagrees with the widely accepted Lenstra–Pomerance–Wagstaff conjecture.

References

Bateman, P. T.; Selfridge, J. L.; Wagstaff Jr., Samuel S. (1989). "The new Mersenne conjecture". American Mathematical Monthly . Mathematical Association of America. 96 (2): 125–128. doi:10.2307/2323195. JSTOR 2323195. MR 0992073.
Dickson, L. E. (1919). History of the Theory of Numbers . Carnegie Institute of Washington. p. 31. OL 6616242M. Reprinted by Chelsea Publishing, New York, 1971, ISBN 0-8284-0086-5.

↑ See the sources given for the individual primes in List of Mersenne primes and perfect numbers.
1 2 "The New Mersenne Prime Conjecture". t5k.org.
↑ Wanless, James. "Mersenneplustwo Factorizations".
↑ 2=2⁰ + 1 satisfies exactly two of the three conditions, but is explicitly excluded from the conjecture due to being even
1 2 Heuristics: Deriving the Wagstaff Mersenne Conjecture. The Prime Pages. Retrieved on 2014-05-11.
↑ Michael Le Page (Aug 10, 2019). "Inside the race to find the first billion-digit prime number". New Scientist.

External links

The Prime Glossary. New Mersenne prime conjecture.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] See the sources given for the individual primes in List of Mersenne primes and perfect numbers.

[auto-2] 1 2 "The New Mersenne Prime Conjecture". t5k.org.

[3] Wanless, James. "Mersenneplustwo Factorizations".

[4] 2=2⁰ + 1 satisfies exactly two of the three conditions, but is explicitly excluded from the conjecture due to being even

[heur-5] 1 2 Heuristics: Deriving the Wagstaff Mersenne Conjecture. The Prime Pages. Retrieved on 2014-05-11.

[6] Michael Le Page (Aug 10, 2019). "Inside the race to find the first billion-digit prime number". New Scientist.

[1]

[2]

[3]

[4]

[5]

[6]