Definition:Mersenne Prime

Definition

A Mersenne prime is a Mersenne number which happens to be prime.

That is, it is a prime number of the form $2^p - 1$.

From Primes of the Form of a Power Less One, it is clear that in order for $2^p - 1$ to be prime, then $p$ must also be prime.

The number $2^p - 1$ is, in this context, often denoted $M_p$.

It is not known whether there is an infinite number of Mersenne primes.

Historical Note

They are named for Marin Mersenne, who published a book Cogitata Physico-Mathematica in 1644, in which he claimed that the only primes $p \le 257$ for which $2^p - 1$ is prime are $2, 3, 5, 7, 13, 17, 19, 31, 67, 127$ and $257$.

He was not entirely correct, as shall be seen.

Previous to that, the special nature of these primes had been noted by Euclid, who showed that if $2^n - 1$ is prime, then $2^{n-1} \left({2^n - 1}\right)$ is perfect. The first four primes of this form were known to him.

The fifth one, $M_{13}$, may have been known to Iamblichus in the 4th century A.D., but this is uncertain, as he does not explicitly demonstrate it. It was definitely known about by 1456.

Pietro Cataldi is supposed to have discovered the 6th and 7th Mersenne primes $M_{17}$ and $M_{19}$ in 1588. Recent researches, however, suggest that these may have already been discovered by 1460. But as no evidence has been found from that date that they had been proven to be prime, it is possible that these were just lucky guesses.

Cataldi also claimed the primality of the Mersenne numbers $M_{23}, M_{29}, M_{31}$ and $M_{37}$. In this he was correct only about $M_{31}$, so it is more than possible he was only guessing.

Work started in earnest on these numbers from Mersenne's work.

• In the 17th century, Fermat showed that $M_{23}$ has $47$ as a divisor, and that $M_{37}$ has $223$ as a factor.

• 1738: Euler showed that $M_{29}$ is composite, having the factor $233$.

• 1772: Euler showed that $M_{31}$ is indeed prime.

• 1811: Peter Barlow (somewhat short-sightedly, given historical 20-20 hindsight) stated in his book Elementary Investigation of the Theory of Numbers that $M_{31}$ "is the the greatest [i.e. Mersenne number] at present known to be such ... and probably the greatest that ever will be discovered." See Barlow's Prediction.

• 1876: Édouard Lucas proved that $M_{127}$ is prime, and also discovered that $M_{67}$ is actually composite.

• 1883: Ivan Pervushin proved that $M_{61}$ is prime.

• 1903: The factors of $M_{67}$ were found by Frank Cole who delivered a now famous lecture On The Factorization of Large Numbers in which he performed (without uttering a word) the arithmetic demonstrating what those factors were.

• 1911: R. E. Powers proved that $M_{89}$ is prime.

• 1914: R. E. Powers proved that $M_{107}$ is prime.

• 1916: R. E. Powers proved that $M_{241}$ is composite.

• 1922: Maurice Kraitchik proved that $M_{257}$ is actually composite.

Thus Mersenne's assertion was finally investigated in full: he had been determined to be wrong by:

• including $M_{67}$ and $M_{257}$ in his list of primes;
• failing to include $M_{61}$, $M_{89}$ and $M_{107}$.

(Pervushin's discovery of the primality of $M_{61}$ caused some to suggest that Mersenne's claim of the primality of $M_{67}$ may have been a copying error for $M_{61}$.)

Nobody will ever know how Mersenne came to his conclusions, as it is impossible with the mathematical knowledge of the time for him to have worked it all out by hand. The fact that he made so few mistakes is incredible.

The work continued, and does so to this day.

• 1952: Raphael Robinson used a computer to show that $M_{521}, M_{607}, M_{1279}, M_{2203}$ and $M_{2281}$ are all prime.

• During the next four decades, the count of known Mersenne primes was doubled by various mathematicians testing supercomputers.

Since then, hunting for Mersenne primes has become a casual hobby for anyone who has access to a computer.

Testing Primality of a Mersenne number

The Lucas-Lehmer Test is a way of determining the primality of a given $M_p$ without laboriously testing each possible prime divisor.

G.I.M.P.S.

"G.I.M.P.S." (Great Internet Mersenne Prime Search), or just "GIMPS", has become a gathering place for Number Theorists interested in the discovery of the Mersenne primes.

In August and September of 2008 alone, both the 45th and 46th Mersenne primes were discovered:

$M_{43,112,609}$ (a 12,978,189 digit number)

and

$M_{37,156,667}$ (an 11,185,272 digit number)

becoming the first Mersenne primes of 10 million digits to be found.

You can follow the work of G.I.M.P.S. at www.mersenne.org.

Currently known Mersenne Primes

	Prime $p$	Prime $M_p$	Number of digits in $M_p$	Date discovered	Discovered by
1	$2$	$3$	$1$	Known to Euclid
2	$3$	$7$	$1$	Known to Euclid
3	$5$	$31$	$2$	Known to Euclid
4	$7$	$127$	$3$	Known to Euclid
5	$13$	$8191$	$4$	1456
6	$17$	$131 \ 071$	$6$	1588	Cataldi
7	$19$	$524 \ 287$	$6$	1588	Cataldi
8	$31$	$2 \ 147 \ 483 \ 647$	$10$	1772	Euler
9	$61$	$2.305 \times 10^{18}$	$19$	1883	Pervushin
10	$89$	$6.189 \times 10^{26}$	$27$	1911	Powers
11	$107$	$1.622 \times 10^{32}$	$33$	1914	Powers
12	$127$	$1.701 \times 10^{38}$	$39$	1876	Lucas
13	$521$	$6.865 \times 10^{156}$	$157$	30 Jan 1952	R. Robinson
14	$607$	$5.311 \times 10^{182}$	$183$	30 Jan 1952	R. Robinson
15	$1279$	$1.041 \times 10^{385}$	$386$	25 Jun 1952	R. Robinson
16	$2203$	$1.476 \times 10^{663}$	$664$	7 Oct 1952	R. Robinson
17	$2281$	$4.461 \times 10^{686}$	$687$	9 Oct 1952	R. Robinson
18	$3217$	$2.591 \times 10^{968}$	$969$	8 Sept 1957	Hans Riesel
19	$4253$	$1.908 \times 10^{1280}$	$1281$	3 Nov 1961	Alexander Hurwitz
20	$4423$	$2.855 \times 10^{1331}$	$1332$	3 Nov 1961	Alexander Hurwitz
21	$9689$	$4.782 \times 10^{2916}$	$2917$	11 May 1963	Donald Gillies
22	$9941$	$3.461 \times 10^{2992}$	$2993$	16 May 1963	Donald Gillies
23	$11 \ 213$	$2.814 \times 10^{3375}$	$3376$	2 Jun 1963	Donald Gillies
24	$19 \ 937$	$4.315 \times 10^{6001}$	$6002$	4 Mar 1971	Bryant Tuckerman
25	$21 \ 701$	$4.487 \times 10^{6532}$	$6533$	30 Oct 1978	Landon Noll and Ariel Nickel
26	$23 \ 209$	$4.029 \times 10^{6986}$	$6987$	9 Feb 1979	Landon Noll
27	$44 \ 497$	$8.545 \times 10^{13 \ 394}$	$13 \ 395$	8 Apr 1979	Harry Nelson and David Slowinski
28	$86 \ 243$	$5.369 \times 10^{25 \ 961}$	$25 \ 962$	25 Sept 1982	David Slowinski
29	$110 \ 503$	$5.219 \times 10^{33 \ 264}$	$33 \ 265$	28 Jan 1988	Walt Colquitt and Luke Welsh
30	$132 \ 049$	$5.127 \times 10^{39 \ 750}$	$39 \ 751$	19 Sept 1983	David Slowinski
31	$216 \ 091$	$7.461 \times 10^{65 \ 049}$	$65 \ 050$	1 Sept 1985	David Slowinski
32	$756 \ 839$	$1.741 \times 10^{227 \ 831}$	$227 \ 832$	19 Feb 1992	David Slowinski and Paul Gage
33	$859\ 433$	$1.295 \times 10^{258\ 715}$	$258\ 716$	4 Jan 1994	David Slowinski and Paul Gage
34	$1\ 257\ 787$	$4.122 \times 10^{378\ 631}$	$378\ 632$	3 Sept 1996	David Slowinski and Paul Gage
35	$1\ 398\ 269$	$8.147 \times 10^{420\ 920}$	$420\ 921$	13 Nov 1996	GIMPS / Joel Armengaud
36	$2\ 976\ 221$	$6.233 \times 10^{895\ 931}$	$895\ 932$	24 Aug 1997	GIMPS / Gordon Spence
37	$3\ 021\ 377$	$1.274 \times 10^{909\ 525}$	$909\ 526$	27 Jan 1998	GIMPS / Roland Clarkson
38	$6\ 972\ 593$	$4.371 \times 10^{2\ 098\ 959}$	$2\ 098\ 960$	1 Jun 1999	GIMPS / Nayan Hajratwala
39	$13\ 466\ 917$	$9.249 \times 10^{4\ 053\ 945}$	$4\ 053\ 946$	14 Nov 2001	GIMPS / Michael Cameron
40	$20\ 996\ 011$	$1.260 \times 10^{6\ 320\ 429}$	$6\ 320\ 430$	17 Nov 2003	GIMPS / Michael Shafer
	$24\ 036\ 583$	$2.994 \times 10^{7\ 235\ 732}$	$7\ 235\ 733$	15 May 2004	GIMPS / Josh Findley
	$25\ 964\ 951$	$1.222 \times 10^{7\ 816\ 229}$	$7\ 816\ 230$	18 Feb 2005	GIMPS / Martin Nowak
	$30\ 402\ 457$	$3.154 \times 10^{9\ 152\ 051}$	$9\ 152\ 052$	15 Dec 2005	GIMPS / Curtis Cooper and Steven Boone
	$32\ 582\ 657$	$1.246 \times 10^{9\ 808\ 358}$	$9\ 808\ 358$	4 Sept 2006	GIMPS / Curtis Cooper and Steven Boone
	$37\ 156\ 667$	$2.023 \times 10^{11\ 185\ 271}$	$11\ 185\ 272$	6 Sept 2008	GIMPS / Hans-Michael Elvenich
	$42\ 643\ 801$	$1.699 \times 10^{12\ 837\ 063}$	$12\ 837\ 064$	12 Apr 2009	GIMPS / Odd Magnar Strindmo
	$43\ 112\ 609$	$3.165 \times 10^{12\ 978\ 188}$	$12\ 978\ 189$	23 Aug 2008	GIMPS / Edson Smith

Note that the index numbers of Mersenne primes after no. 40 are uncertain, as there may still be undiscovered Mersenne primes between the 39th and 47th. Not all numbers in that range have been explored yet.

Also see

This sequence is A001348 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).