Mersenne Prime

A Mersenne Number which is Prime is called a Mersenne prime. In order for the Mersenne number $M_n$ defined by

$$M_n\equiv 2^n-1$$

for $n$ an Integer to be Prime, $n$ must 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 and can be factored. Every Mersenne Prime gives rise to a Perfect Number.

If $n\equiv 3\ \left({{\rm mod\ } {4}}\right)$ 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). A Prime factor $p$ of a Mersenne number $M_q=2^q-1$ is a Wieferich Prime Iff $p^2\vert 2^q-1$, Therefore, Mersenne Primes are not Wieferich Primes. All known Mersenne numbers $M_p$ with $p$ Prime are Squarefree. However, Guy (1994) believes that there are $M_p$ which are not Squarefree.

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.

It has been conjectured that there exist an infinite number of Mersenne primes, although finding them is computationally very challenging. The table below gives the index $p$ of known Mersenne primes (Sloane's A000043) $M_p$, 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 35th known Mersenne prime has not been completely searched, so identification of ``the'' 36th Mersenne prime is tentative. L. Welsh maintains an extensive bibliography and history of Mersenne numbers. G. Woltman has organized a distributed search program via the Internet in which hundreds of volunteers use their personal computers to perform pieces of the search.

#	$p$	Digits	Year	Published 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	1952	Lehmer 1952-3, Robinson 1952
14	607	183	1952	Lehmer 1952-3, Robinson 1952
15	1279	386	1952	Lehmer 1952-3, Robinson 1952
16	2203	664	1952	Lehmer 1952-3, Robinson 1952
17	2281	687	1952	Lehmer 1952-3, Robinson 1952
18	3217	969	1957	Riesel 1957
19	4253	1281	1961	Hurwitz 1961
20	4423	1332	1961	Hurwitz 1961
21	9689	2917	1963	Gillies 1964
22	9941	2993	1963	Gillies 1964
23	11213	3376	1963	Gillies 1964
24	19937	6002	1971	Tuckerman 1971
25	21701	6533	1978	Noll and Nickel 1980
26	23209	6987	1979	Noll 1980
27	44497	13395	1979	Nelson and Slowinski 1979
28	86243	25962	1982	Slowinski 1982
29	110503	33265	1988	Colquitt and Welsh 1991
30	132049	39751	1983	Slowinski 1988
31	216091	65050	1985	Slowinski 1989
32	756839	227832	1992	Gage and Slowinski 1992
33	859433	258716	1994	Gage and Slowinski 1994
34	1257787	378632	1996	Slowinski and Gage
35	1398269	420921	1996	Armengaud, Woltman, et al.
36?	2976221	895832	1997	Spence
37?	3021377	909526	1998	Clarkson, Woltman, et al.

See also Cunningham Number, Fermat-Lucas Number, Fermat Number, Fermat Number (Lucas), Fermat Polynomial, Lucas-Lehmer Test, Mersenne Number, Perfect Number, Repunit, Superperfect Number

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.

Caldwell, C. ``Mersenne Primes: History, Theorems and Lists.'' http://www.utm.edu/research/primes/mersenne.shtml.

Caldwell, C. ``GIMPS Finds a Prime! $2^{1398269}-1$ is Prime.'' http://www.utm.edu/research/primes/notes/1398269/.

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.

Gillies, D. B. ``Three New Mersenne Primes and a Statistical Theory.'' Math Comput. 18, 93-97, 1964.

Guy, R. K. ``Mersenne Primes. Repunits. Fermat Numbers. Primes of Shape $k\cdot 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.

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. ftp://sable.ox.ac.uk/pub/math/factors/mersenne.

Mersenne, M. Cogitata Physico-Mathematica. 1644.

Mersenne Organization. ``GIMPS Discovers 36th Known Mersenne Prime, $2^{2976221}-1$ is Now the Largest Known Prime.'' http://www.mersenne.org/2976221.htm.

Mersenne Organization. ``GIMPS Discovers 37th Known Mersenne Prime, $2^{3021377}-1$ is Now the Largest Known Prime.'' http://www.mersenne.org/3021377.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.

Sloane, N. J. A. Sequence A000043/M0672 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

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.

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. ``Mersenne Numbers.'' Mathematica notebook Mersenne.m.

Welsh, L. ``Marin Mersenne.'' http://www.scruznet.com/~luke/mersenne.htm.

Welsh, L. ``Mersenne Numbers & Mersenne Primes Bibliography.'' http://www.scruznet.com/~luke/biblio.htm.

Woltman, G. ``The GREAT Internet Mersenne Prime Search.'' http://www.mersenne.org/prime.htm.