TOPICS
Search

Mersenne Prime

A Mersenne prime is a Mersenne number, i.e., a number of the form

M_n=2^n-1,

that is prime. In order for M_n to be prime, n must itself be prime. This is true since for composite n with factors r and s, n=rs. Therefore, 2^n-1 can be written as 2^(rs)-1, which is a binomial number that always has a factor (2^r-1).

The first few Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ... (OEIS A000668) corresponding to indices n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, ... (OEIS A000043).

Mersenne primes were first studied because of the remarkable properties that every Mersenne prime corresponds to exactly one perfect number. L. Welsh maintains an extensive bibliography and history of Mersenne numbers.

MersennePrimeDensity

It has been conjectured that there exist an infinite number of Mersenne primes. Fitting a line through the origin to the asymptotic number of Mersenne primes M_p with p<=lnx for the first 51 (known) Mersenne primes gives a best-fit line with c(x)=2.51763lnx, illustrated above. If the line is not restricted to pass through the origin, the best fit is (-2.27+/-0.51)+(2.68+/-0.04)lnx. It has been conjectured (without any particularly strong evidence) that the constant is given by e^gammasqrt(2)=2.518..., where gamma is the Euler-Mascheroni constant (Havil 2003, p. 116; Caldwell), a result related to Wagstaff's conjecture.

Mersenne postmark

However, finding Mersenne primes is computationally very challenging. For example, the 1963 discovery that M_(11213) is prime was heralded by a special postal meter design, illustrated above, issued in Urbana, Illinois.

G. Woltman has organized a distributed search program via the Internet known as GIMPS (Great Internet Mersenne Prime Search) in which hundreds of volunteers use their personal computers to perform pieces of the search. The efforts of GIMPS volunteers make this distributed computing project the discoverer of all of the Mersenne primes discovered since late 1996. As of Oct. 21, 2024, GIMPS participants have tested and verified all exponents below 69 million and tested all exponents below 124 million at least once (GIMPS).

The table below gives the index p of known Mersenne primes (OEIS A000043) M_p, together with the number of digits, discovery years, and discoverer. A similar table has been compiled by C. Caldwell. Note that sequential indexing of "the" nth Mersenne prime is tentative for n=49 until all exponents between M_(48) and M_(49) (namely up to 74207281) have been verified to be composite. Ranked indices are therefore also tentative for the larger known Mersenne primes M_(50), M_(51), and M_(52).

#pdigitsyeardiscoverer (reference)value
121antiquity3
231antiquity7
352antiquity31
473antiquity127
51341461Reguis (1536), Cataldi (1603)8191
61761588Cataldi (1603)131071
71961588Cataldi (1603)524287
831101750Euler (1772)2147483647
961191883Pervouchine (1883), Seelhoff (1886)2305843009213693951
1089271911Powers (1911)618970019642690137449562111
11107331913Powers (1914)162259276829213363391578010288127
12127391876Lucas (1876)170141183460469231731687303715884105727
13521157Jan. 30, 1952Robinson (1954)68647976601306097149...12574028291115057151
14607183Jan. 30, 1952Robinson (1954)53113799281676709868...70835393219031728127
151279386Jun. 25, 1952Robinson (1954)10407932194664399081...20710555703168729087
162203664Oct. 7, 1952Robinson (1954)14759799152141802350...50419497686697771007
172281687Oct. 9, 1952Robinson (1954)44608755718375842957...64133172418132836351
183217969Sep. 8, 1957Riesel25911708601320262777...46160677362909315071
1942531281Nov. 3, 1961Hurwitz19079700752443907380...76034687815350484991
2044231332Nov. 3, 1961Hurwitz28554254222827961390...10231057902608580607
2196892917May 11, 1963Gillies (1964)47822027880546120295...18992696826225754111
2299412993May 16, 1963Gillies (1964)34608828249085121524...19426224883789463551
23112133376Jun. 2, 1963Gillies (1964)28141120136973731333...67391476087696392191
24199376002Mar. 4, 1971Tuckerman (1971)43154247973881626480...36741539030968041471
25217016533Oct. 30, 1978Noll and Nickel (1980)44867916611904333479...57410828353511882751
26232096987Feb. 9, 1979Noll (Noll and Nickel 1980)40287411577898877818...36743355523779264511
274449713395Apr. 8, 1979Nelson and Slowinski85450982430363380319...44867686961011228671
288624325962Sep. 25, 1982Slowinski53692799550275632152...99857021709433438207
2911050333265Jan. 28, 1988Colquitt and Welsh (1991)52192831334175505976...69951621083465515007
3013204939751Sep. 20, 1983Slowinski51274027626932072381...52138578455730061311
3121609165050Sep. 6, 1985Slowinski74609310306466134368...91336204103815528447
32756839227832Feb. 19, 1992Slowinski and Gage17413590682008709732...02603793328544677887
33859433258716Jan. 10, 1994Slowinski and Gage12949812560420764966...02414267243500142591
341257787378632Sep. 3, 1996Slowinski and Gage41224577362142867472...31257188976089366527
351398269420921Nov. 12, 1996Joel Armengaud/GIMPS81471756441257307514...85532025868451315711
362976221895832Aug. 24, 1997Gordon Spence/GIMPS62334007624857864988...76506256743729201151
373021377909526Jan. 27, 1998Roland Clarkson/GIMPS12741168303009336743...25422631973024694271
3869725932098960Jun. 1, 1999Nayan Hajratwala/GIMPS43707574412708137883...35366526142924193791
39134669174053946Nov. 14, 2001Michael Cameron/GIMPS92494773800670132224...30073855470256259071
40209960116320430Nov. 17, 2003Michael Shafer/GIMPS12597689545033010502...94714065762855682047
41240365837235733May 15, 2004Josh Findley/GIMPS29941042940415717208...67436921882733969407
42259649517816230Feb. 18, 2005Martin Nowak/GIMPS12216463006127794810...98933257280577077247
43304024579152052Dec. 15, 2005Curtis Cooper and Steven Boone/GIMPS31541647561884608093...11134297411652943871
44325826579808358Sep. 4, 2006Curtis Cooper and Steven Boone/GIMPS12457502601536945540...11752880154053967871
453715666711185272Sep. 6, 2008Hans-Michael Elvenich/GIMPS20225440689097733553...21340265022308220927
464264380112837064Jun. 12, 2009Odd Magnar Strindmo/GIMPS16987351645274162247...84101954765562314751
474311260912978189Aug. 23, 2008Edson Smith/GIMPS31647026933025592314...80022181166697152511
485788516117425170Jan. 25, 2013Curtis Cooper/GIMPS58188726623224644217...46141988071724285951
49?7420728122338618Jan. 7, 2016Curtis Cooper/GIMPS30037641808460618205...87010073391086436351
50?7723291723249425Dec. 26, 2017Jonathan Pace/GIMPS46733318335923109998...82730618069762179071
51?8258993324862048Dec. 7, 2018Patrick Laroche/GIMPS14889444574204132554...37951210325217902591
52?13627984141024320Oct. 12, 2024Luke Durant/GIMPS88169432750383326555...55076706219486871551

Trial division is often used to establish the compositeness of a potential Mersenne prime. This test immediately shows M_p to be composite for p=11, 23, 83, 131, 179, 191, 239, and 251 (with small factors 23, 47, 167, 263, 359, 383, 479, and 503, respectively). A much more powerful primality test for M_p is the Lucas-Lehmer test.

If n=3 (mod 4) is a prime, then 2n+1 divides M_n iff 2n+1 is prime. It is also true that prime divisors of 2^p-1 must have the form 2kp+1 where k is a positive integer and simultaneously of either the form 8n+1 or 8n-1 (Uspensky and Heaslet 1939).

A prime factor p of a Mersenne number M_q=2^q-1 is a Wieferich prime iff p^2|2^q-1. Therefore, Mersenne primes are not Wieferich primes.

See also

Catalan-Mersenne Number, Cullen Number, Cunningham Number, Double Mersenne Number, Eberhart's Conjecture, Fermat-Lucas Number, Fermat Number, Fermat Polynomial, Integer Sequence Primes, Lucas-Lehmer Test, Mersenne Number, New Mersenne Prime Conjecture, Perfect Number, Repunit, Superperfect Number, Titanic Prime, Wagstaff's Conjecture, Woodall Prime

Explore with Wolfram|Alpha

References

Bateman, P. T.; Selfridge, J. L.; and Wagstaff, S. S. "The New Mersenne Conjecture." Amer. Math. Monthly 96, 125-128, 1989.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 66, 1987.Beiler, A. H. Ch. 3 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Bell, E. T. Mathematics: Queen and Servant of Science. Washington, DC: Math. Assoc. Amer., 1987.Caldwell, C. "Mersenne Primes: History, Theorems and Lists." http://www.utm.edu/research/primes/mersenne/.Caldwell, C. K. "The Top Twenty: Mersenne Primes." http://www.utm.edu/research/primes/lists/top20/Mersenne.html.Caldwell, C. "Where Is the Next Mersenne Prime?" http://primes.utm.edu/notes/faq/NextMersenne.html.Colquitt, W. N. and Welsh, L. Jr. "A New Mersenne Prime." Math. Comput. 56, 867-870, 1991.Conway, J. H. and Guy, R. K. "Mersenne's Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 135-137, 1996.Devlin, K. "World's Largest Prime." FOCUS: Newsletter Math. Assoc. Amer. 17, 1, Dec. 1997.Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, p. 13, 2005.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, pp. 47-51, 2000.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, p. 85, 1984.Gardner, M. "Patterns in Primes Are a Clue to the Strong Law of Small Numbers." Sci. Amer. 243, 18-28, Dec. 1980.Gillies, D. B. "Three New Mersenne Primes and a Statistical Theory." Math Comput. 18, 93-97, 1964.GIMPS. "GIMPS Milestones Report." http://v5www.mersenne.org/report_milestones/.Great Internet Prime Search: GIMPS. Finding World World Primes Since 1996. "List of Known Mersenne Prime Numbers." http://www.mersenne.org/primes/.Guy, R. K. "Mersenne Primes. Repunits. Fermat Numbers. Primes of Shape k·2^n+2 [sic]." §A3 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 8-13, 1994.Haghighi, M. "Computation of Mersenne Primes Using a Cray X-MP." Intl. J. Comput. Math. 41, 251-259, 1992.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 14-16, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Kraitchik, M. "Mersenne Numbers and Perfect Numbers." §3.5 in Mathematical Recreations. New York: W. W. Norton, pp. 70-73, 1942.Kravitz, S. and Berg, M. "Lucas' Test for Mersenne Numbers 6000<p<7000." Math. Comput. 18, 148-149, 1964.Lehmer, D. H. "On Lucas's Test for the Primality of Mersenne's Numbers." J. London Math. Soc. 10, 162-165, 1935.Leyland, P. http://research.microsoft.com/~pleyland/factorization/factors/mersenne.txt.Mersenne, M. Cogitata Physico-Mathematica. 1644.Noll, C. and Nickel, L. "The 25th and 26th Mersenne Primes." Math. Comput. 35, 1387-1390, 1980.Powers, R. E. "The Tenth Perfect Number." Amer. Math. Monthly 18, 195-196, 1911.Powers, R. E. "Note on a Mersenne Number." Bull. Amer. Math. Soc. 40, 883, 1934.Robinson, R. M. "Mersenne and Fermat Numbers." Proc. Amer. Math. Soc. 5, 842-846, 1954.Shankland, S. "Cooperative Computing Finds Top Prime Number." ZDNet News: Hardware. Dec. 2, 2003. http://zdnet.com.com/2100-1103_2-5112827.html?tag=zdfd.newsfeed.Sloane, N. J. A. Sequences A000043/M0672 and A000668/M2696 in "The On-Line Encyclopedia of Integer Sequences."Slowinski, D. "Searching for the 27th Mersenne Prime." J. Recreat. Math. 11, 258-261, 1978-1979.Tuckerman, B. "The 24th Mersenne Prime." Proc. Nat. Acad. Sci. USA 68, 2319-2320, 1971.Uhler, H. S. "A Brief History of the Investigations on Mersenne Numbers and the Latest Immense Primes." Scripta Math. 18, 122-131, 1952.Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.Welsh, L. "Marin Mersenne." http://www.utm.edu/research/primes/mersenne/LukeMirror/mersenne.htm.Welsh, L. "Mersenne Numbers & Mersenne Primes Bibliography." http://www.utm.edu/research/primes/mersenne/LukeMirror/biblio.htm.Whitehouse, D. "Number Takes Prime Position." December 5, 2001. BBC News online. http://news.bbc.co.uk/hi/english/sci/tech/newsid_1693000/1693364.stm.Woltman, G. "The GREAT Internet Mersenne Prime Search." http://www.mersenne.org/prime.htm.

Referenced on Wolfram|Alpha

Mersenne Prime

Cite this as:

Weisstein, Eric W. "Mersenne Prime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MersennePrime.html

Subject classifications