Definition:Mersenne Prime

From ProofWiki
Jump to: navigation, search

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

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


Index of Mersenne Prime

The index of the Mersenne prime $M_p = 2^p - 1$ is the (prime) number $p$.


History of Mersenne Primes

Mersenne primes 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 $4$th century A.D.[1], 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 $6$th and $7$th Mersenne primes $M_{17}$ and $M_{19}$ in $1588$. Recent researches[2], 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}$.[3] In this he was correct only about $M_{31}$, so that also backs up the suggestion that he was only guessing.


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

  • In the $17$th 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.
  • $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.


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

  • $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.

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

It was founded by George F. Woltman in early $1996$.

All the Mersenne primes discovered from November $1996$ onwards have been discovered by this team.

In particular August and September of $2008$ alone, both the $45$th and $46$th 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 Pietro Antonio Cataldi
7 $19$ $524 \, 287$ $6$ 1588 Pietro Antonio Cataldi
8 $31$ $2 \, 147 \, 483 \, 647$ $10$ 1772 Leonhard Paul Euler
9 $61$ $2 \cdotp 305 \times 10^{18}$ $19$ 1883 Ivan Mikheevich Pervushin
10 $89$ $6 \cdotp 189 \times 10^{26}$ $27$ 1911 R.E. Powers
11 $107$ $1 \cdotp 622 \times 10^{32}$ $33$ 1914 R.E. Powers
12 $127$ $1 \cdotp 701 \times 10^{38}$ $39$ 1876 Édouard Lucas
13 $521$ $6 \cdotp 865 \times 10^{156}$ $157$ 30 Jan 1952 Raphael Mitchel Robinson
14 $607$ $5 \cdotp 311 \times 10^{182}$ $183$ 30 Jan 1952 Raphael Mitchel Robinson
15 $1279$ $1 \cdotp 041 \times 10^{385}$ $386$ 25 Jun 1952 Raphael Mitchel Robinson
16 $2203$ $1 \cdotp 476 \times 10^{663}$ $664$ 7 Oct 1952 Raphael Mitchel Robinson
17 $2281$ $4 \cdotp 461 \times 10^{686}$ $687$ 9 Oct 1952 Raphael Mitchel Robinson
18 $3217$ $2 \cdotp 591 \times 10^{968}$ $969$ 8 Sept 1957 Hans Ivar Riesel
19 $4253$ $1 \cdotp 908 \times 10^{1280}$ $1281$ 3 Nov 1961 Alexander Hurwitz
20 $4423$ $2 \cdotp 855 \times 10^{1331}$ $1332$ 3 Nov 1961 Alexander Hurwitz
21 $9689$ $4 \cdotp 782 \times 10^{2916}$ $2917$ 11 May 1963 Donald Bruce Gillies
22 $9941$ $3 \cdotp 461 \times 10^{2992}$ $2993$ 16 May 1963 Donald Bruce Gillies
23 $11 \, 213$ $2 \cdotp 814 \times 10^{3375}$ $3376$ 2 Jun 1963 Donald Bruce Gillies
24 $19 \, 937$ $4 \cdotp 315 \times 10^{6001}$ $6002$ 4 Mar 1971 Bryant Tuckerman
25 $21 \, 701$ $4 \cdotp 487 \times 10^{6532}$ $6533$ 30 Oct 1978 Landon Curt Noll and Ariel Nickel
26 $23 \, 209$ $4 \cdotp 029 \times 10^{6986}$ $6987$ 9 Feb 1979 Landon Curt Noll
27 $44 \, 497$ $8 \cdotp 545 \times 10^{13 \, 394}$ $13 \, 395$ 8 Apr 1979 Harry Lewis Nelson and David Slowinski
28 $86 \, 243$ $5 \cdotp 369 \times 10^{25 \, 961}$ $25 \, 962$ 25 Sept 1982 David Slowinski
29 $110 \, 503$ $5 \cdotp 219 \times 10^{33 \, 264}$ $33 \, 265$ 28 Jan 1988 Walt Colquitt and Luke Welsh
30 $132 \, 049$ $5 \cdotp 127 \times 10^{39 \, 750}$ $39 \, 751$ 19 Sept 1983 David Slowinski
31 $216 \, 091$ $7 \cdotp 461 \times 10^{65 \, 049}$ $65 \, 050$ 1 Sept 1985 David Slowinski
32 $756 \, 839$ $1 \cdotp 741 \times 10^{227 \, 831}$ $227 \, 832$ 19 Feb 1992 David Slowinski and Paul Gage
33 $859 \, 433$ $1 \cdotp 295 \times 10^{258 \, 715}$ $258 \, 716$ 4 Jan 1994 David Slowinski and Paul Gage
34 $1 \, 257 \, 787$ $4 \cdotp 122 \times 10^{378 \, 631}$ $378 \, 632$ 3 Sept 1996 David Slowinski and Paul Gage
35 $1 \, 398 \, 269$ $8 \cdotp 147 \times 10^{420 \, 920}$ $420 \, 921$ 13 Nov 1996 GIMPS / Joel Armengaud
36 $2 \, 976 \, 221$ $6 \cdotp 233 \times 10^{895 \, 931}$ $895 \, 932$ 24 Aug 1997 GIMPS / Gordon Spence
37 $3 \, 021 \, 377$ $1 \cdotp 274 \times 10^{909 \, 525}$ $909 \, 526$ 27 Jan 1998 GIMPS / Roland Clarkson
38 $6 \, 972 \, 593$ $4 \cdotp 371 \times 10^{2 \, 098 \, 959}$ $2 \, 098 \, 960$ 1 Jun 1999 GIMPS / Nayan Hajratwala
39 $13 \, 466 \, 917$ $9 \cdotp 249 \times 10^{4 \, 053 \, 945}$ $4 \, 053 \, 946$ 14 Nov 2001 GIMPS / Michael Cameron
40 $20 \, 996 \, 011$ $1 \cdotp 260 \times 10^{6 \, 320 \, 429}$ $6 \, 320 \, 430$ 17 Nov 2003 GIMPS / Michael Shafer
41 $24 \, 036 \, 583$ $2 \cdotp 994 \times 10^{7 \, 235 \, 732}$ $7 \, 235 \, 733$ 15 May 2004 GIMPS / Josh Findley
42 $25 \, 964 \, 951$ $1 \cdotp 222 \times 10^{7 \, 816 \, 229}$ $7 \, 816 \, 230$ 18 Feb 2005 GIMPS / Martin Nowak
43 $30 \, 402 \, 457$ $3 \cdotp 154 \times 10^{9 \, 152 \, 051}$ $9 \, 152 \, 052$ 15 Dec 2005 GIMPS / Curtis Cooper and Steven Boone
44 $32 \, 582 \, 657$ $1 \cdotp 246 \times 10^{9 \, 808 \, 358}$ $9 \, 808 \, 358$ 4 Sept 2006 GIMPS / Curtis Cooper and Steven Boone
45 $37 \, 156 \, 667$ $2 \cdotp 023 \times 10^{11 \, 185 \, 271}$ $11 \, 185 \, 272$ 6 Sept 2008 GIMPS / Hans-Michael Elvenich
$42 \, 643 \, 801$ $1 \cdotp 699 \times 10^{12 \, 837 \, 063}$ $12 \, 837 \, 064$ 12 Apr 2009 GIMPS / Odd Magnar Strindmo
$43 \, 112 \, 609$ $3 \cdotp 165 \times 10^{12 \, 978 \, 188}$ $12 \, 978 \, 189$ 23 Aug 2008 GIMPS / Edson Smith
$57 \, 885 \, 161$ $5 \cdotp 818 \times 10^{17 \, 425 \, 169}$ $17 \, 425 \, 170$ 25 Jan 2013 GIMPS / Curtis Cooper
$74 \, 207 \, 281$ $3 \cdotp 003 \times 10^{22 \, 338 \, 617}$ $22 \, 338 \, 618$ 07 Jan 2016 GIMPS / Curtis Cooper
$77 \, 232 \, 917$ $23 \, 249 \, 425$ 26 Dec 2017 GIMPS / Jon Pace

Note that the index numbers of Mersenne primes after no. $45$ are uncertain, as there may still be undiscovered Mersenne primes between the $45$th and $49$th.

Not all numbers in that range have been explored yet.


Also see

  • Results about Mersenne primes can be found here.


Source of Name

This entry was named for Marin Mersenne.


References

  1. 1908: Sir Thomas L. Heath: Euclid: The Thirteen Books of The Elements: footnote to Book $\text{IX}$ Proposition $36$.
  2. Ettore Picutti, in Historia Mathematica pp $123$ - $136$ ($1989$), records that an anonymous author had discovered by $1460$ that both $M_{17}$ and $M_{19}$ are prime.
  3. See The Largest Known Prime by Year.
  4. See Chris Caldwell's website The Prime Pages for more detail of the history of the unearthing of Mersenne primes, and more.


Sources