Mersenne conjectures

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]^[4]^[5] 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^[6]	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.

p	p=2^k +/- 1 or p=4^k +/- 3	2^p - 1 prime	(2^p + 1)/3 prime
3	yes (-1)	yes	yes
5	yes (+1)	yes	yes
7	yes (-1/+3)	yes	yes
11	no	no factor: 23	yes
13	yes (-3)	yes	yes
17	yes (+1)	yes	yes
19	yes (+3)	yes	yes
23	no	no factor: 47	yes
31	yes (-1)	yes	yes
43	no	no factor: 431	yes
61	yes (-3)	yes	yes
67	yes (+3)	no factor: 193707721	no factor: 7327657
79	no	no factor: 2687	yes
89	no	yes	no factor: 179
101	no	no factor: 7432339208719	yes
107	no	yes	no factor: 643
127	yes (-1)	yes	yes
167	no	no factor: 2349023	yes
191	no	no factor: 383	yes
199	no	no factor: 164504919713	yes
257	yes (+1)	no factor: 535006138814359	no factor: 37239639534523
313	no	no factor: 10960009	yes
347	no	no factor: 14143189112952632419639	yes
521	no	yes	no factor: 501203
607	no	yes	no factor: 115331
701	no	no factor: 796337	yes
1021	yes (-3)	no factor: 40841	no factor: 10211
1279	no	yes	no factor: 706009
1709	no	no factor: 379399	yes
2203	no	yes	no factor: 13219
2281	no	yes	no factor: 22811
2617	no	no factor: 78511	yes
3217	no	yes	no factor: 7489177
3539	no	no factor: 7079	yes
4093	yes (-3)	no factor: 2397911088359	no factor: 3732912210059
4099	yes (+3)	no factor: 73783	no factor: 2164273
4253	no	yes	no factor: 118071787
4423	no	yes	no factor: 2827782322058633
5807	no	no factor: 139369	yes
8191	yes (-1)	no factor: 338193759479	no (prp test) no factor (P-1 B1=10^10 B2=10^12)
9689	no	yes	no factor: 19379
9941	no	yes	no factor: 11120148512909357034073
10501	no	no factor: 2160708549249199	yes
10691	no	no factor: 21383	yes
11213	no	yes	no factor: 181122707148161338644285289935461939
11279	no	no factor: 2198029886879	yes
12391	no	no factor: 198257	yes
14479	no	no factor: 27885728233673	yes
16381	yes (-3)	no factor: 8114899840326779533679915276470289950126585679	no factor: 163811
19937	no	yes	no (prp test) no factor < 2^59 (ECM t=50digits)
21701	no	yes	no factor: 43403
23209	no	yes	no factor: 4688219
42737	no	no factor: 542280975142237477071005102443059419300063	yes
44497	no	yes	no factor: 2135857
65537	yes (+1)	no factor: 513668017883326358119	no factor: 13091975735977
65539	yes (+3)	no factor: 3354489977369	no factor: 58599599603
83339	no	no factor: 166679	yes
86243	no	yes	no factor: 1627710365249
95369	no	no factor: 297995890279	yes
110503	no	yes	no factor: 48832113344350037579071829046935480686609
117239	no	no no factor < 2^65 (ECM t=35digits)	yes
127031	no	no factor: 12194977	yes
131071	yes (-1)	no factor: 231733529	no factor: 2883563
132049	no	yes	no factor: 618913299601153
138937	no	no factor: 100068818503	yes
141079	no	no factor: 458506751	yes (prp)
216091	no	yes	no factor: 10704103333093885136919332089553661899
262147	yes (+3)	no factor: 268179002471	no factor: 4194353
267017	no	no factor: 1602103	yes (prp)
269987	no	no factor: 1940498230606195707774295455176153	yes (prp)
374321	no	no no factor < 2^65 (ECM t=35digits)	yes (prp)
524287	yes (+1)	no factor: 62914441	no (prp test) no factor < 2^70
756839	no	yes	no factor: 1640826953
859433	no	yes	no factor: 1718867
986191	no	no no factor < 2^67 (ECM t=35digits)	yes (prp)
1048573	yes (-3)	no factor: 73400111	no (prp test) no factor < 2^70
1257787	no	yes	no factor: 20124593
1398269	no	yes	no factor: 23609117451215727502931
2976221	no	yes	no factor: 434313978089
3021377	no	yes	no factor: 95264016811
4031399	no	no factor: 8062799	yes (prp)
4194301	yes (-3)	no factor: 2873888432993463577	no factor: 14294177809
6972593	no	yes	no factor: 142921867730820791335455211
13347311	no	no factor: 26694623	yes (prp)
13372531	no	no factor: 451135705817	yes (prp)
13466917	no	yes	no factor: 781081187
15135397	no	no no factor < 2^70	yes (prp)
16777213	yes (-3)	no no factor < 2^75	no factor: 68470872139190782171
20996011	no	yes	no factor: 50965926368055564259063193
24036583	no	yes	no factor: 11681779339
25964951	no	yes	no factor: 155789707
30402457	no	yes	no (prp test) no factor < 2^70 (ECM t=25digits)
32582657	no	yes	no factor: 13526662966442476828963
37156667	no	yes	no factor: 297253337
42643801	no	yes	no factor: 405661842777846034141594389769
43112609	no	yes	no factor: 86225219
57885161	no	yes	no factor: 7061989643
74207281	no	yes	no (prp test) no factor < 2^79 (ECM t=25digits)
77232917	no	yes	no factor: 3460697185562027
82589933	no	yes	no factor: 17973642059656480077259129
136279841	no	yes	no factor: 7827576937344589790262450890609
268435459	yes (+3)	no (prp test) no factor < 2^83	no factor: 414099276471761
1073741827	yes (+3)	no factor: 16084529043983099051873383	unknown no factor < 2^84
2147483647	yes (-1)	no factor: 295257526626031	unknown no factor < 2^86
M61	yes (-1)	unknown no factor < 2280000000000000000M61^[7]	no factor: 1328165573307087715777
M127	yes (-1)	unknown no factor < 22^60M127^[8]	no factor: 886407410000361345663448535540258622490179142922169401

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),

^[9]

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).

^[9]

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,^[10] 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).

References

Bateman, P. T.; Selfridge, J. L.; Wagstaff Jr., Samuel S. (1989). "The new Mersenne conjecture". American Mathematical Monthly. 96 (2). Mathematical Association of America: 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.
^ ^a ^b "The New Mersenne Prime Conjecture". t5k.org.
^ Wanless, James. "Mersenneplustwo Factorizations".
^ Höglund, Andreas. "New Mersenne Conjecture".
^ Status of the "New Mersenne Conjecture"
^ 2=2⁰ + 1 satisfies exactly two of the three conditions, but is explicitly excluded from the conjecture due to being even
^ status of the double Mersenne number MM61
^ status of the double Mersenne number MM127
^ ^a ^b 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.

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

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

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

[4] Höglund, Andreas. "New Mersenne Conjecture".

[5] Status of the "New Mersenne Conjecture"

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

[7] status of the double Mersenne number MM61

[8] status of the double Mersenne number MM127

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

[10] 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]

[7]

[8]

[9]

[10]

Original Mersenne conjecture

New Mersenne conjecture

Lenstra–Pomerance–Wagstaff conjecture

See also

References

External links