Number Theory > Numbers > Large Numbers v
Number Theory > Prime Numbers > Prime Number Sequences v
Number Theory > Special Numbers > Prime-Related Numbers v


Mersenne Prime

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


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

The first few Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ... (Sloane's A000668) corresponding to indices n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, ... (Sloane's 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.

It has been conjectured that there exist an infinite number of Mersenne primes. Fitting a line to the asymptotic number of Mersenne primes with gives a best-fit line with . It has been conjectured (without any particularly strong evidence) that the constant is given by , where is the Euler-Mascheroni constant (Havil 2003, p. 116), though is actually significantly closer to the numerical fit.

However, finding Mersenne primes is computationally very challenging. For example, the 1963 discovery that 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. On November 17, 2003, almost exactly two years after the previous find, a GIMPS volunteer reported discovery of the 40th Mersenne prime, a discovery that was subsequently confirmed. Almost exactly six months later, discovery of the 41st known Mersenne prime by a GIMPS volunteer was announced. Discovery of the 42nd known Mersenne prime was announced by Woltman on Feb. 18, 2005, but has yet to be confirmed. The efforts of GIMPS volunteers make this distributed computing project the discoverer of all seven of the largest known Mersenne primes. In fact, as of Feb. 2005, GIMPS participants have tested and double-checked all exponents below and tested all exponents below at least once (GIMPS).

The table below gives the index p of known Mersenne primes (Sloane's A000043) , together with the number of digits, discovery years, and discoverer. A similar table has been compiled by C. Caldwell. Note that the region after the 38th known Mersenne prime has not been completely searched, so identification of "the" 40th Mersenne prime is tentative (GIMPS).

# p digits year discoverer (reference)
1 2 1 antiquity  
2 3 1 antiquity  
3 5 2 antiquity  
4 7 3 antiquity  
5 13 4 1461 Reguis (1536), Cataldi (1603)
6 17 6 1588 Cataldi (1603)
7 19 6 1588 Cataldi (1603)
8 31 10 1750 Euler (1772)
9 61 19 1883 Pervouchine (1883), Seelhoff (1886)
10 89 27 1911 Powers (1911)
11 107 33 1913 Powers (1914)
12 127 39 1876 Lucas (1876)
13 521 157 Jan. 30, 1952 Robinson
14 607 183 Jan. 30, 1952 Robinson
15 1279 386 Jan. 30, 1952 Robinson
16 2203 664 Jan. 30, 1952 Robinson
17 2281 687 Jan. 30, 1952 Robinson
18 3217 969 Sep. 8, 1957 Riesel
19 4253 1281 Nov. 3, 1961 Hurwitz
20 4423 1332 Nov. 3, 1961 Hurwitz
21 9689 2917 May 11, 1963 Gillies (1964)
22 9941 2993 May 16, 1963 Gillies (1964)
23 11213 3376 Jun. 2, 1963 Gillies (1964)
24 19937 6002 Mar. 4, 1971 Tuckerman (1971)
25 21701 6533 Oct. 30, 1978 Noll and Nickel (1980)
26 23209 6987 Feb. 9, 1979 Noll (Noll and Nickel 1980)
27 44497 13395 Apr. 8, 1979 Nelson and Slowinski (Slowinski 1978-79)
28 86243 25962 Sep. 25, 1982 Slowinski
29 110503 33265 Jan. 28, 1988 Colquitt and Welsh (1991)
30 132049 39751 Sep. 20, 1983 Slowinski
31 216091 65050 Sep. 6, 1985 Slowinski
32 756839 227832 Feb. 19, 1992 Slowinski and Gage
33 859433 258716 Jan. 10, 1994 Slowinski and Gage
34 1257787 378632 Sep. 3, 1996 Slowinski and Gage
35 1398269 420921 Nov. 12, 1996 Joel Armengaud/GIMPS
36 2976221 895832 Aug. 24, 1997 Gordon Spence/GIMPS (Devlin 1997)
37 3021377 909526 Jan. 27, 1998 Roland Clarkson/GIMPS
38 6972593 2098960 Jun. 1, 1999 Nayan Hajratwala/GIMPS
39 13466917 4053946 Nov. 14, 2001 Michael Cameron/GIMPS (Whitehouse 2001, Weisstein 2001ab)
40? 20996011 6320430 Nov. 17, 2003 Michael Shafer/GIMPS (Weisstein 2003ab)
41? 24036583 7235733 May 15, 2004 Josh Findley/GIMPS (Weisstein 2004)
42? - - Feb. 18, 2005 GIMPS (Weisstein 2005)

Trial division is often used to establish the compositeness of a potential Mersenne prime. This test immediately shows 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 is the Lucas-Lehmer test.

If is a prime, then divides iff is prime. It is also true that prime divisors of must have the form where k is a positive integer and simultaneously of either the form or (Uspensky and Heaslet 1939).

A prime factor p of a Mersenne number is a Wieferich prime iff . Therefore, Mersenne primes are not Wieferich primes.

Catalan-Mersenne Number, Cunningham Number, Double Mersenne Number, Fermat-Lucas Number, Fermat Number, Fermat Polynomial, Integer Sequence Primes, Lucas-Lehmer Test, Mersenne Number, Perfect Number, Repunit, Superperfect Number, Titanic Prime




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. "GIMPS Finds a Prime! Is Prime." http://www.utm.edu/research/primes/notes/1398269/.

Caldwell, C. "GIMPS Finds a Multi-Million Digit Prime!." http://www.utm.edu/research/primes/notes/6972593/.

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: Chelsea, p. 13, 1952.

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 Status." http://www.mersenne.org/status.htm.

Guy, R. K. "Mersenne Primes. Repunits. Fermat Numbers. Primes of Shape [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 ." 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.

Mersenne Organization. "GIMPS Discovers 36th Known Mersenne Prime, Is Now the Largest Known Prime." http://www.mersenne.org/2976221.htm.

Mersenne Organization. "GIMPS Discovers 37th Known Mersenne Prime, Is Now the Largest Known Prime." http://www.mersenne.org/3021377.htm.

Mersenne Organization. "GIMPS Finds First Million-Digit Prime, Stakes Claim to EFF Award. Is Now the Largest Known Prime." http://www.mersenne.org/6972593.htm.

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.

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." http://www.research.att.com/~njas/sequences/.

Slowinski, D. "Searching for the 27th Mersenne Prime." J. Recreat. Math. 11, 258-261, 1978-1979.

Slowinski, D. Sci. News 139, 191, 9/16/1989.

Spiegel Online: Wissenschaft. "Student entdeckt bisher größte Primzahl." Dec. 3, 2003. http://www.spiegel.de/wissenschaft/mensch/0,1518,276682,00.html.

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.

Weisstein, E. W. "New Mersenne Prime (Probably) Discovered." MathWorld Headline News, Nov. 19, 2001a. ../topics/news/2003-11-19/mersenne/.

Weisstein, E. W. "New Mersenne Prime Announced." MathWorld Headline News, Dec. 5, 2001b. ../topics/news/2001-12-05/mersenne/.

Weisstein, E. W. "40th Mersenne Prime (Probably) Discovered." MathWorld Headline News, Nov. 19, 2003a. ../topics/news/2003-11-19/mersenne/.

Weisstein, E. W. "40th Mersenne Announced." MathWorld Headline News, Dec. 2, 2003b. ../topics/news/2003-12-02/mersenne/.

Weisstein, E. W. "41st Mersenne Announced." MathWorld Headline News, Jun. 1, 2004. ../topics/news/2004-06-01/mersenne/.

Weisstein, E. W. "42nd Mersenne Prime (Probably) Discovered." MathWorld Headline News, Feb. 18, 2005. ../topics/news/2005-02-18/mersenne/.

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:// 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.