Mersenne-Primzahl
Eine Mersenne-Primzahl ist eine Primzahl, die eins weniger als die Zweierpotenz einer Primzahl ist. Beispielsweise ist 3 = 22-1 eine Mersenne-Primzahl, genau wie 7 = 23-1. Der kleinste prime Exponent, der auf keine Mersenne-Primzahl führt, ist 11: 211-1=2047 ist faktorisierbar als 2047 = 23 · 89.Allgemeiner nennt man die Zahl Mp:=2p-1 die pte Mersenne-Zahl. Mit dieser Bezeichnungsweise sind die Mersenne-Primzahlen genau die Mersenne-Zahlen, die Primzahlen sind.
Den Namen haben diese Primzahlen von dem französischen Mönch und Priester Marin Mersenne (1588 - 1648), der behauptete, dass für p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 und 257 Mp eine Primzahl ist. Dabei irrte er aber bei den Zahlen 67 und 257 und übersah die Zahlen 61, 89 und 107.
Daß M67 keine Primzahl ist, wurde erst im Jahre 1903 vom Mathematiker Cole entdeckt. Um den Nachweis zu führen, daß M257 keine Primzahl ist, wurde 1932 eine frühe Rechenmaschine verwendet.
Bei der Zahl 67 handelt es sich möglicherweise um einen Lesefehler seitens Mersenne aus seiner Korrespondenz mit Frenicle de Bessy und Fermat, wobei er p=61 verwechselte mit p=67.
Expertenabschnitt: Dieser Abschnitt enthält tiefergehende Informationen, für die zum Teil zusätzliches Fachwissen notwendig ist. Der Beweis der oben genannten Eigenschaft ergibt sich folgendermaßen: Wenn p=rs zusammengesetzt ist, dann gilt:
Zwei weitere Eigenschaften von Mersennezahlen sind die folgenden:
Letztere wurde von Euler formuliert, aber erst später von Lagrange bewiesen. Außerdem ist noch bekannt:
|
Neben der Tatsache, dass die größten bekannten Primzahlen Mersenne-Zahlen sind, spielen diese eine wichtige Rolle im Zusammenhang mit perfekten Zahlen. Dies wird im Artikel über perfekte Zahlen genauer erläutert.
Da für Mersenne-Zahlen ein besonders einfacher Primzahltest existiert, nämlich der Lucas-Lehmer-Test, eignen sich diese Zahlen für die Suche nach Primzahlrekorden. Der Lucas-Lehmer-Test basiert ganz wesentlich darauf, dass die Mersenne-Zahlen im Binärsystem nur aus lauter Einsen bestehen, also, wenn man so will, die binären Schnapszahlen sind.
Der Lucas-Lehmer-Test funktioniert wie folgt:
Wir prüfen mit diesem Verfahren, ob M5 = 25-1 = 31 eine Primzahl ist.
Bisher kennt man 41 Mersenne-Primzahlen. Mit Computerhilfe versucht man, weitere Mersenne-Primzahlen zu finden.
Da es sich um sehr große Zahlen handelt - die 40. Mersenne-Primzahl ist mehrere Millionen Ziffern lang - sind die Berechnungen sehr aufwändig.
Rechenoperationen mit derart großen Zahlen werden von Computern nicht von Hause aus unterstützt.
Man muss die Zahlen in großen Feldern abspeichern und die damit erforderlichen Grundrechenarten programmieren.
Dies führt zu sehr langen Programmlaufzeiten.
GIMPS (Great Internet Mersenne Prime Search) versucht daher, weltweit möglichst viele Computer an den Berechnungen zu beteiligen und stellt die erforderliche Software für eine Reihe von Plattformen (Windows, Unix, Linux ...) zur Verfügung.
Jeder kann mitmachen, sofern er einen Rechner mit (zeitweise) freien CPU-Kapazitäten besitzt.
Dazu muss man sich von der Website die Software herunterladen und dann installieren.
Danach meldet man sich bei GIMPS und lässt sich eine Zahl geben, die man untersuchen soll.
Wenn die Berechnungen erledigt sind (meist nach mehreren Wochen oder Monaten) meldet man das Ergebnis bei GIMPS zurück.
Anwendungen
Die Suche nach Mersenne-Primzahlen
Der Lucas-Lehmer-Test
In dieser von D. H. Lehmer gefundenen Form, die auf E. Lucas zurück geht, ist die Anwendung allerdings unpraktisch, weil die Zahlen S(k)) sehr schnell sehr groß werden. Deshalb wird heutzutage das Verfahren dahingehend abgewandelt, dass bereits alle Zwischenschritte modulo M(p) ausgerechnet werden, und damit derart große Zahlen vermieden werden:Beispiel
S(1) = 4
S(2) = 42 - 2 mod 31 = 14 mod 31 = 14
S(3) = 142 - 2 mod 31 = 194 mod 31 = 8
S(4) = 82 - 2 mod 31 = 62 mod 31 = 0
Da S(4) = 0 ist, ist M5 = 31 also eine Primzahl.Literatur zum Lucas-Lehmer-Test
Suche nach Mersenne-Primzahlen: GIMPS
Vermutungen zu den Mersenne-Zahlen
Diese besagt, dass aus zwei der folgenden drei Aussagen bereits die dritte folgt:
Weblinks
Geschichte der Mersenne-Primzahlen als Tabelle
Jahr | Ereignis |
---|---|
bis 1536 | Man glaubt, dass für alle Primzahlen p gilt, 2p-1 sei prim. |
1536 | Hudalricus Regius zeigt, dass 211-1 keine Primzahl ist, obwohl 11 prim ist. |
1603 | Pietro Cataldi (1548 - 1626) zeigt, dass 2n-1 Primzahlen sind für n=17,19. Fälschlicherweise glaubte er dies auch für n=23,29,31,37. (ist nur für n=31 korrekt) |
1640 | Fermat widerlegte Cataldi für n=23 und n=37: 223-1 und 237-1 sind doch keine Primzahlen. |
1644 | Mersenne behauptet, 2n - 1 sei prim für n = 2,3,5,7,13,17,19,31,67,127 und 257, jedoch nicht prim für alle anderen natürlichen Zahlen kleiner als 257 (Vorwort zu seinem Werk "Cogitata Physica-Mathematica"). Dies ist allerdings falsch, denn 2n-1 ist prim sowohl für n=61 (was 1883 bemerkt wird) als auch für n=89,107 (wird erst nach 1900 nachgewiesen) |
1738 | Euler widerlegt Cataldi für n=29. |
1750 | Euler bestätigt, dass Cataldi für n=31 richtig lag: 231 - 1 ist prim. |
1870 | Edouard Lucas (1842 - 1891) formuliert die theoretischen Grundlagen für den Lucas-Lehmer Test. |
1876 | Lucas bestätigt Mersenne: 2127-1 ist prim. |
1883 | M. Pervouchine (orthodoxer Priester in Perm/Russland) zeigt, dass 261-1 prim ist (Widerspruch zu Mersenne). |
1911 | R.E. Powers widerspricht Mersenne für n=89: 2n-1 ist prim. |
1914 | Powers widerspricht Mersenne auch für n=107: 2n-1 ist prim. Fast gleichzeitig kommt auch E. Fauquembergue zu dieser Aussage |
1930 | Lehmer (1867-1938) formuliert den Lucas-Lehmer Test. |
1932 | Lehmer zeigt: M(149) und M(257) sind nicht prim. |
1934 | Powers zeigt: M(241) ist nicht prim. |
1944 | H.S.Uhler zeigt: M(157) und M(167) sind nicht prim. |
1945 | H.S.Uhler zeigt: M(229) ist nicht prim. |
1947 | H.S.Uhler zeigt: M(199) ist nicht prim. |
1947 | Der Bereich von 1 bis 258 wird vollständig überprüft. Man kennt nun die Mersenne-Primzahlen für n=2,3,5,7,13,17,19,31,61,89,107 und 127. |
1951 | Beginn des Einsatzes von Computern |
1999 | Mit M(6972593) kennt man erstmals eine Primzahl mit mehr als 1 Million Stellen. |
2004 | M(24036583) wird gefunden, die bis jetzt (Mai 2004) größte bekannte Mersenne-Primzahl. |
Liste aller bekannter Mersenne-Primzahlen
Nr. | n | Anz.Ziffern von M(n) | Anz.Ziffern der perf.Zahl k(n) | Jahr | Entdecker |
---|---|---|---|---|---|
1 | 2 | 1 | 1 | - | - |
2 | 3 | 1 | 2 | - | - |
3 | 5 | 2 | 3 | - | - |
4 | 7 | 3 | 4 | - | - |
5 | 13 | 4 | 8 | 1456 | - |
6 | 17 | 6 | 10 | 1588 | Cataldi |
7 | 19 | 6 | 12 | 1588 | Cataldi |
8 | 31 | 10 | 19 | 1772 | Euler |
9 | 61 | 19 | 37 | 1883 | Pervushin |
10 | 89 | 27 | 54 | 1911 | Powers |
11 | 107 | 33 | 65 | 1914 | Powers |
12 | 127 | 39 | 77 | 1876 | Lucas |
13 | 521 | 157 | 314 | 1952 | Robinson |
14 | 607 | 183 | 366 | 1952 | Robinson |
15 | 1279 | 386 | 770 | 1952 | Robinson |
16 | 2203 | 664 | 1327 | 1952 | Robinson |
17 | 2281 | 687 | 1373 | 1952 | Robinson |
18 | 3217 | 969 | 1937 | 1957 | Riesel |
19 | 4253 | 1281 | 2561 | 1961 | Hurwitz |
20 | 4423 | 1332 | 2663 | 1961 | Hurwitz |
21 | 9689 | 2917 | 5834 | 1963 | Gillies |
22 | 9941 | 2993 | 5985 | 1963 | Gillies |
23 | 11213 | 3376 | 6751 | 1963 | Gillies |
24 | 19937 | 6002 | 12003 | 1971 | Tuckerman |
25 | 21701 | 6533 | 13066 | 1978 | Noll + Nickel |
26 | 23209 | 6987 | 13973 | 1979 | Noll |
27 | 44497 | 13395 | 26790 | 1979 | Nelson + David Slowinski |
28 | 86243 | 25962 | 51924 | 1982 | David Slowinski |
29 | 110503 | 33265 | 66530 | 1988 | Colquitt + Welsh |
30 | 132049 | 39751 | 79502 | 1983 | David Slowinski |
31 | 216091 | 65050 | 130100 | 1985 | David Slowinski |
32 | 756839 | 227832 | 455663 | 1992 | David Slowinski + Gage |
33 | 859433 | 258716 | 517430 | 1994 | David Slowinski + Gage |
34 | 1257787 | 378632 | 757263 | 1996 | David Slowinski + Gage |
35 | 1398269 | 420921 | 841842 | 1996 | Joel Armengaud + George Woltman + GIMPS |
36 | 2976221 | 895932 | 1791864 | 1997 | Gordon Spence + George Woltman + GIMPS |
37 | 3021377 | 909526 | 1819050 | 1998 | Roland Clarkson + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
38 | 6972593 | 2098960 | 4197919 | 1999 | Nayan Hajratwala + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
? | 13466917 | 4053946 | 8107892 | 2001 | Michael Cameron + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
? | 20996011 | 6320430 | 12640859 | 2003 | Michael Shafer + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
? | 24036583 | 7235733 | 14471466 | 2004 | Josh Findley + George Woltman + Scott Kurowski + GIMPS, PrimeNet |