Mersenne number
A Mersenne number is a number of the form . In particular, the -th Mersenne number is used. The first seven Mersenne numbers are
The prime numbers among the Mersenne numbers are called Mersenne prime numbers . The first eight Mersenne primes are
When shown in the dual system , Mersenne numbers appear as columns of one , i.e. H. Numbers that consist entirely of ones. The -th Mersenne number is a number with ones in the dual system (example:) . In binary , Mersenne numbers belong to the number palindromes , Mersenne prime numbers accordingly belong to the prime number palindromes .
P: M _{p} is Mersenne number -: M _{p} is the composite Mersenne number Cyan shows right Pink shows wrong |
||||||||
p | 2 | 3 | 5 | 7th | 11 | 13 | 17th | 19th |
---|---|---|---|---|---|---|---|---|
M _{p} | P | P | P | P | - | P | P | P |
p | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
M _{p} | - | - | P | - | - | - | - | - |
p | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
M _{p} | - | P | - | - | - | - | - | P |
p | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
M _{p} | - | - | - | P | - | - | P | - |
p | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
M _{p} | - | - | - | - | - | - | - | - |
p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
M _{p} | - | - | - | - | - | - | - | - |
p | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
M _{p} | - | - | - | - | - | - | - | - |
These prime numbers get their name from the French monk and priest Marin Mersenne (1588–1648), who claimed in the foreword of his Cogitata Physico-Mathematica that the number is a prime number for and .
However, he was wrong about the numbers and and overlooked the Mersenne prime numbers , and . Édouard Lucas showed in 1876 that there is no prime number , but it was not until 1903 that the mathematician Frank Nelson Cole was able to name the prime factors of this number. In 1932, an early calculating machine was used to prove that it is not a prime number. The number is possibly a reading error on the part of Mersenne from his correspondence with Bernard Frénicle de Bessy and Pierre de Fermat , which he confused with .
Mersenne numbers are also used in the Mersenne twister , a pseudo-random number generator .
history
Mersenne numbers were first studied in the ancient world in the context of perfect numbers . A natural number is called perfect if it is equal to the sum of its proper factors (example:) . Even Euclid had shown that the number is complete if a prime number is ( provides the number ). 2000 years later, Euler showed the converse for even perfect numbers: every even perfect number is of the form where is a prime number.
Odd perfect numbers have not yet been found, but their existence has not yet been proven or refuted.
The first four perfect numbers and were already known in ancient times. The search for further perfect numbers motivated the search for further Mersenne prime numbers. The most important property to consider is the following:
- Is a composite number , then is also a composite number. That by and by is divided without a remainder can be shown with the help of a polynomial division if and are natural numbers without the zero.
It follows immediately that the exponent of a Mersenne prime is itself a prime. This property makes the search for Mersenne prime numbers easier, since only Mersenne numbers with prime exponents have to be considered.
However, the inverse conclusion that is prime when is prime is incorrect because, for example, is not prime.
Mersenne prime numbers are rare : so far (December 2018) only 51 have been found. Since there is a particularly efficient test of prime numbers for them, the largest known prime numbers are Mersenne prime numbers.
year | event |
---|---|
until 1536 | It is believed that for all prime numbers p it holds that 2 ^{p} −1 is prime. |
1536 | The German arithmetic master Ulrich Rieger (lat. Hudalrichus Regius) published in his arithmetic book Utriusque Arithmetices epitome as the first the fifth perfect number 2 ^{12} · (2 ^{13} -1) = 4096 · 8191 = 33550336 in printed form. Since the numbers 511 and 2047 do not appear in his tabular overview, one can assume that he recognized 2 ^{11} –1 = 2047 = 23 · 89 as compound, although he does not mention this separately. |
1555 | Johann Scheubel publishes in his German translation of Books VII-IX of Euclid's Elements the next two perfect numbers 2 ^{16} · (2 ^{17} -1) = 65536 · 131071 = 8589869056 and 2 ^{18} · (2 ^{19} -1) = 262144 · 524287 = 137438691328. The second factors are the Mersenne prime numbers M _{17} and M _{19} . However, he did not recognize both 2 ^{11} -1 = 2047 = 23 · 89, and 2 ^{15} -1 = 32767 = 7 · 31 · 151 as composite, but instead 2 ^{21} -1 = 2097151 = 7 ^{2} · 127 · 337. (He does not give the decompositions at this point, however.) In his work, he incorrectly receives nine instead of the correct seven perfect numbers. |
1603 | Pietro Cataldi (1548–1626) shows that 2 ^{p} –1 is prime for p = 17, 19 and correctly suspects this for p = 31. He wrongly believes it also for p = 23, 29 and 37. |
1640 | Fermat refutes Cataldi for p = 23 and p = 37: 2 ^{23} -1 = 47 · 178481 and 2 ^{37} -1 = 223 · 616318177 are not prime numbers. |
1644 | Mersenne claims that 2 ^{p} –1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, but not prime for all other natural numbers less than 257 (preface to his work Cogitata Physico-Mathematica ). Today we know that this claim is wrong, because 2 ^{p} –1 is prime both for p = 61 (Perwuschin, 1883) and for p = 89 (Powers, 1911) and p = 107 (Powers and Fauquembergue, 1914) , 2 ^{67} –1 is also composed (Lucas, 1876; Cole 1903). |
1738 | Euler refutes Cataldi for p = 29: 2 ^{29} -1 = 233 1103 2089. |
1750 | Euler confirms that Cataldi was correct for p = 31: 2 ^{31} –1 is prime. |
1870 | Édouard Lucas (1842–1891) formulates the theoretical basis for the Lucas-Lehmer test . |
1876 | Lucas confirms Mersenne: 2 ^{127} -1 is prime and contradicts: 2 ^{67} -1 is not prime, factors remain unknown. |
1883 | Ivan Michejowitsch Pervuschin (1827–1900), a Russian mathematician and Orthodox priest from Perm / Russia, shows that 2 ^{61} –1 is prime (contradicting Mersenne). |
1903 | Frank Nelson Cole names the prime factors of 2 ^{67} -1 = 193707721 · 761838257287. |
1911 | Ralph Ernest Powers contradicts Mersenne for p = 89: 2 ^{p} –1 is prime. |
1914 | Powers also contradicts Mersenne for p = 107: 2 ^{p} –1 is prime. Almost at the same time E. Fauquembergue comes to this statement. |
1930 | Derrick Henry Lehmer (1905–1991) formulates the Lucas-Lehmer test. |
1932 | Lehmer shows: M (149) and M (257) are not prime, he calculates two hours a day on a desk calculator for a year . |
1934 | Powers shows: M (241) is not prime. |
1944 | Horace S. Uhler shows: M (157) and M (167) are not prime. |
1945 | Uhler shows: M (229) is not prime. |
1947 | Uhler shows: M (199) is not prime. |
1947 | The range from 1 to 257 is now fully checked. We now know the Mersenne prime numbers M ( p ) for p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127. |
1951 | Start of using computers. The length of the largest known prime number increased from 39 places to 687 decimal places by 1952. |
1963 | Donald Gillies discovers M (11,213) with 3,376 digits. |
1996 | With GIMPS, Joel Armengaud and George Woltman discover M (1,398,269) with 420,921 digits. |
1999 | With M (6,972,593), which has 2,098,960 digits, a prime number with more than 1 million digits is known for the first time on June 1st. |
2004 | On May 15, it is proven that M (24,036,583), a number with 7,235,733 digits, is prime. |
2005 | On February 18, the GIMPS project discovered the 42nd Mersenne prime: M (25,964,951) has 7,816,230 digits.
The GIMPS project also discovered the 43rd Mersenne prime number on December 15: M (30,402,457) has 9,152,052 digits. |
2006 | On September 4, the GIMPS project reported the discovery of the 44th Mersenne prime M (32,582,657) with 9,808,358 digits. |
2008 | On September 16, the GIMPS project published the 45th and 46th known Mersenne prime numbers: M (37,156,667) (discovered on September 6) with 11,185,272 digits and M (43,112,609) (discovered on September 6th) August 23) with 12,978,189 positions. |
2009 | The 47th known Mersenne prime M (42,643,801) was discovered by the GIMPS project on April 12th and published on June 12th. |
2013 | The 48th known Mersenne prime M (57,885,161) is discovered by the GIMPS project on January 25th. |
2016 | The 49th known Mersenne prime M (74,207,281) is discovered by the GIMPS project on January 7th. |
2017 | The 50th known Mersenne prime M (77,232,917) is discovered by the GIMPS project on December 26th. |
2018 | The 51st known Mersenne prime M (82,589,933) is discovered by the GIMPS project on December 7th. |
Divisibility properties of the Mersenne numbers
In the course of its long history, many results have been found on Mersenne numbers. Besides the already mentioned basic property of divisibility (divides the number , then is a divisor of ) there are e.g. B. the following results:
- If an even number and prime, then a divisor of , e.g. B. .
- Is an odd prime and a prime factor of M _{n} , so true and . Example: and ._{}
- If is a prime number with , then the following equivalence applies: divides the Mersenne number if and only if is prime. Example: is prime and passes a remainder of when divided . Since (as a result of ) is prime, it follows: divides the Mersenne number . This statement was formulated by Leonhard Euler , but only later proved by Joseph-Louis Lagrange ( see also Sophie-Germain prime number ).
- If a prime number, then it is not a prime number (namely divisible by). Mersenne prime numbers are therefore not suitable as the smaller prime number of a prime twin .
- If with , the product of the Fermat numbers is up . Example: .
The search for Mersenne prime numbers
Mersenne primes are particularly suitable for achieving prime number records in several ways because (a) composite exponents can be ignored because they do not generate prime numbers, and therefore a list of the candidates for the exponent can easily be created with prime number generators , (b) from this list as above described Sophie Germain prime numbers with can be separated (eg. p = 11 → divider 23), (c) by the functional relationship of the order of the prime number exponentially - namely to the base two - grows with the argument that very large numbers are obtained quickly, (d) the Lucas-Lehmer test described below is a simple and effective prime number test .
The Lucas-Lehmer test
This test is a prime number test specially tailored to Mersenne numbers, based on the work of Édouard Lucas from the period 1870–1876 and supplemented in 1930 by Derrick Henry Lehmer .
It works like this:
- Be odd and prime. The consequence is defined by .
- Then: is a prime number if and only if is divisible by .
GIMPS: The Great Internet Mersenne Prime Number Search
As of December 2018, 51 Mersenne prime numbers are known. With the help of a computer one tries to find further Mersenne prime numbers. Since the numbers are very large - the 51st Mersenne prime number has more than 24 million digits in the decimal system - the calculations are time-consuming and time-consuming. Arithmetic operations with such large numbers are not inherently supported by computers. You have to save the numbers in large fields and program the necessary basic arithmetic operations . This leads to long program runtimes.
GIMPS ( English : G reat I nternet M ersenne P rime S earch) therefore tries to involve as many computers as possible worldwide in the calculations. The software required for this ( Prime95 ) was created by George Woltman and Scott Kurowski and is available for a number of computer platforms (Windows, Unix, Linux ...).
Anyone can take part, provided they have a computer with (temporarily) free CPU capacities. To do this, you have to download the software from the website and then install it. Then you log in to GIMPS and get a number to examine. When the calculations are done (usually after several months), the result is reported back to GIMPS. In the course of the computer analysis, you are also given probabilities: the probability of finding a prime number (very small, below 1%); the probability of finding a factor (greater). This probability is intended to make the chances of success for finding a prime number clear.
List of all known Mersenne prime numbers
No. | p | Number of digits of M ( p ) |
year | Explorer |
---|---|---|---|---|
1 | 2 | 1 | - | - |
2 | 3 | 1 | - | - |
3 | 5 | 2 | - | - |
4th | 7th | 3 | - | - |
5 | 13 | 4th | 1456 | - |
6th | 17th | 6th | 1555 | Johann Scheubel |
7th | 19th | 6th | 1555 | Johann Scheubel |
8th | 31 | 10 | 1772 | Leonhard Euler |
9 | 61 | 19th | 1883 | Ivan Pervushin |
10 | 89 | 27 | 1911 | Ralph E. Powers |
11 | 107 | 33 | 1914 | Powers |
12 | 127 | 39 | 1876 | Édouard Lucas |
13 | 521 | 157 | 1952 | Raphael M. Robinson |
14th | 607 | 183 | 1952 | Robinson |
15th | 1279 | 386 | 1952 | Robinson |
16 | 2203 | 664 | 1952 | Robinson |
17th | 2281 | 687 | 1952 | Robinson |
18th | 3217 | 969 | 1957 | Hans Riesel |
19th | 4253 | 1281 | 1961 | Alexander Hurwitz |
20th | 4423 | 1332 | 1961 | Hurwitz |
21st | 9689 | 2917 | 1963 | Donald B. Gillies |
22nd | 9941 | 2993 | 1963 | Gillies |
23 | 11,213 | 3376 | 1963 | Gillies |
24 | 19,937 | 6002 | 1971 | Bryant Tuckerman |
25th | 21,701 | 6533 | 1978 | Landon Curt Noll , Laura Nickel |
26th | 23.209 | 6987 | 1979 | Noll |
27 | 44,497 | 13,395 | 1979 | David Slowinski , Harry L. Nelson |
28 | 86,243 | 25,962 | 1982 | Slowinski |
29 | 110.503 | 33,265 | 1988 | Walter Colquitt , Luther Welsh Jr. |
30th | 132.049 | 39,751 | 1983 | Slowinski |
31 | 216.091 | 65,050 | 1985 | Slowinski |
32 | 756.839 | 227.832 | 1992 | Slowinski, Paul Gage |
33 | 859.433 | 258.716 | 1994 | Slowinski, Paul Gage |
34 | 1,257,787 | 378.632 | 1996 | Slowinski, Paul Gage |
35 | 1,398,269 | 420.921 | 1996 | GIMPS / Joel Armengaud |
36 | 2,976,221 | 895.932 | 1997 | GIMPS / Gordon Spence |
37 | 3,021,377 | 909.526 | 1998 | GIMPS / Roland Clarkson |
38 | 6,972,593 | 2,098,960 | 1999 | GIMPS / Nayan Hajratwala |
39 | 13,466,917 | 4,053,946 | 2001 | GIMPS / Michael Cameron |
40 | 20.996.011 | 6.320.430 | 2003 | GIMPS / Michael Shafer |
41 | 24,036,583 | 7,235,733 | 2004 | GIMPS / Josh Findley |
42 | 25,964,951 | 7,816,230 | 2005 | GIMPS / Martin Nowak |
43 | 30,402,457 | 9,152,052 | 2005 | GIMPS / Curtis Cooper, Steven Boone |
44 | 32,582,657 | 9,808,358 | 2006 | GIMPS / Curtis Cooper, Steven Boone |
45 | 37.156.667 | 11.185.272 | 2008 | GIMPS / Hans-Michael Elvenich |
46 | 42.643.801 | 12,837,064 | 2009 | GIMPS / Odd M. Strindmo |
47 | 43.112.609 | 12,978,189 | 2008 | GIMPS / Edson Smith |
48? | 57.885.161 | 17,425,170 | 2013 | GIMPS / Curtis Cooper |
49? | 74.207.281 | 22,338,618 | 2016 | GIMPS / Curtis Cooper |
50? | 77.232.917 | 23.249.425 | 2017 | GIMPS / Jonathan Pace |
51? | 82,589,933 | 24,862,048 | 2018 | GIMPS / Patrick Laroche |
As of March 13, 2020, it cannot be ruled out that between n = 43,112,609 and n = 82,589,933 there are still further, as yet undiscovered Mersenne prime numbers; therefore the numbering from no. 48 is still uncertain (and marked with a "?").
Open questions
As is so often the case in number theory, there are unsolved problems with Mersenne numbers that are very easy to formulate:
- Are there infinitely many Mersenne prime numbers? On the basis of plausible heuristics, one suspects that there are many Mersenne prime numbers with (for a positive constant ). If so, there would actually be an infinite number of Mersenne prime numbers.
- More precisely, is the conjecture that HW Lenstra and C. Pomerance independently made correct that there are asymptotically many Mersenne prime numbers that are less than or equal to?
- Conversely: are there an infinite number of Mersenne numbers with prime that are not prime? Here, too, the answer is assumed to be yes. This would follow, for example, from the conjecture that there are an infinite number of Sophie-Germain primes that are congruent 3 modulo 4.
- If all Mersenne numbers with prime are square-free , i.e. H. does each prime factor appear exactly once in the prime factorization of the number? So far, it has not even been possible to prove that this applies to an infinite number of Mersenne numbers.
- Does the “new Mersenne conjecture” apply? The sequence of Mersenne prime numbers given by Mersenne suggests that he meant that a Mersenne number with prime is prime if and only if or . Since this statement does not hold, P. Bateman , J. Selfridge and S. Wagstaff made the new Mersenne conjecture.
- This means that the third follows from two of the following three statements:
- or ,
- is a (Mersenne) prime number,
- is a prime number (it is called Wagstaff prime ).
- This means that the third follows from two of the following three statements:
- Are all terms of the sequence prime? The stronger presumption that all numbers are prime numbers for which a prime number could be refuted in 1957 by Raphael Robinson. (e.g. is not prime) These latter numbers are called double Mersenne numbers (OEIS, A077585 ). So far, double Mersenne prime numbers are only known for (OEIS, A077586 ); for and small factors were found. It remains unknown whether there are more or even an infinite number of double Mersenne prime numbers.
literature
- Paulo Ribenboim : The new book of prime number records. 3rd edition. Springer, New York NY a. a. 1996, ISBN 0-387-94457-5 (German: The world of prime numbers. Secrets and records. Updated by Wilfrid Keller. 2nd completely revised and updated edition. Springer, Berlin et al. 2011, ISBN 978-3- 642-18078-1 (Springer textbook) ).
- How a new Mersenne prime was discovered . In: taz , March 11, 2005; dpa background report
Web links
- Prime Mersenne Numbers - History, theorem and Lists (English)
- Great Internet Mersenne Prime Search (GIMPS) and GIMPS Update
- Steffen Haugk's German GIMPS blog in UK
- Mersenne Prime Numbers Bibliography with links to the original publications
- Eric W. Weisstein : Mersenne prime numbers . In: MathWorld (English).
- mprint5 - fast calculation of Mersenne prime numbers by the Finn Mikko Tommila
- Wiki about Mersenne primes and the search (English)
Individual evidence
- ^ Marin Mersenne: Cogitata Physico-Mathematica. In quibus tam naturae quàm artis effectus admirandi certissimis demonstrationibus explicantur. Paris: Bertier, 1644, Praefatio generalis , no.XIX.
- ↑ Hudalrichus Regius: Vtrivsque Arithmetices epitome ex uarijs authoribus concinnata. Strasbourg: Bartholomäus Grüninger, 1536, pp. VIIIv-IXv, chap. 6 (De perfecto [On the perfect numbers]).
- ↑ Johann Scheubel: The sibend, eight and nine books, of the highly famous Mathematici Euclidis Megarensis, in which the operations and rules of all common accounting, for the reason and the foundation, are encouraged to please all those who love the art of accounting [...] Brought to Teütsch out of Latin, and illustrated with common examples, so that any common computer can easily understand and use it. Valentin Ottmar, Augsburg 1555, S. CCXXXI-CXXXIIII (Euclid IX, 36) , here S. CCXXXIII.
- ^ Ralph Ernest Powers: The Tenth Perfect Number. In: American Mathematical Monthly , 18, 1911, No. 11, pp. 195-197.
- ↑ Ralph Ernest Powers: A Mersenne prime. (PDF; 89 kB) In: Bulletin of the American Mathematical Society , 20, 1914, p. 531. Ralph Ernest Powers: Certain composite Mersenne's numbers. In: Proceedings of the London Mathematical Society , 15, 1916, No. 2, pp. Xxii; E. Fauquembergue: Nombres de Mersenne. In: Sphinx-Œdipe , 9, 1914, pp. 103-105; 15, 1920, pp. 17-18. Chris K. Caldwell: M _{107} : Fauquembergue or Powers?
- ^ Derrick Henry Lehmer: Note on Mersenne Numbers. (PDF; 145 kB) In: Bulletin of the American Mathematical Society , 38, 1932, pp. 383-384.
- ↑ pentagon.kappamuepsilon.org ( Memento of the original from October 22, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF)
- ^ Ralph Ernest Powers: Note on a Mersenne Number. (PDF; 69 kB) In: Bulletin of the American Mathematical Society , 40, 1934, p. 883.
- ^ Horace S. Uhler: A New Result Concerning a Mersenne Number. In: Mathematical Tables and other Aids to Computation 1 (1944), pp. 333, 404. Cf. Charles B. Barker: Proof that the Mersenne Number M167 is Composite. (PDF; 70 kB) In: Bulletin of the American Mathematical Society , 51, 1945, p. 389. HS Uhler: Note on the Mersenne Numbers M157 and M167. (PDF; 107 kB) In: Bulletin of the American Mathematical Society , 52, 1946, p. 178.
- ^ Horace S. Uhler: A New Result Concerning a Mersenne Number. In: Mathematical Tables and other Aids to Computation 2 (1945), p. 94.
- ↑ Horace S. Uhler: On Mersenne's Number M199 and Lucas's Sequences. (PDF; 212 kB) In: Bulletin of the American Mathematical Society , 53, 1947, pp. 163-164.
- ↑ Horace S. Uhler: On All of Mersenne's Numbers Particularly M _{193} . (PDF; 200 kB) In: Proceedings of the National Academy of Sciences , 34, 1948, pp. 102-103. Horace S. Uhler: On Mersenne's Number M227 and Cognate Data. (PDF; 320 kB) In: Bulletin of the American Mathematical Society , 54, 1948, No. 4, pp. 378-380. Raymond Clare Archibald : Mersenne Numbers. In: Mathematical Tables and other Aids to Computation , 3, 1949, p. 398.
- ↑ Donald B. Gillies: Three New Mersenne Primes and a Statistical Theory. In: Mathematics of Computation , 18, 1964, pp. 93-97. Bryant Tuckerman: Corrections. In: Mathematics of Computation , 31, 1977, p. 1051.
- ↑ ^{a } ^{b} Andreas Stiller: New largest known prime number found with over 22 million digits. In: heise online. Retrieved January 20, 2016 .
- ↑ ^{a } ^{b } ^{c} GIMPS: Discovery of the 50th known Mersenne Prime. Retrieved January 3, 2018 .
- ↑ Mersenne Prime Discovery - 2 ^ 82589933-1 is Prime! December 21, 2018, accessed December 22, 2018 .
- ↑ 23.2 million: jobs electrical engineer discovered record prime number
- ↑ ^{a } ^{b } List of known Mersenne prime numbers - PrimeNet. Retrieved December 28, 2018 .
- ^ C. Pomerance: Recent developments in primality testing . In: Math. Intelligencer , 3: 3, 1980/81, pp. 97-105.
- ↑ Eric W. Weisstein: Double Mersenne Number . MathWorld (English)