Mersenne-Primzahl
aus Wikipedia, der freien Enzyklopädie
Eine Mersenne-Primzahl ist eine Primzahl der Form 2p–1. 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 Mn:=2n–1 die n-te 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. Dass M67 keine Primzahl ist, wurde erst im Jahre 1903 vom Mathematiker Frank Cole (1861-1926) entdeckt. Um den Nachweis zu führen, dass 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 mit p=67 verwechselte.
Inhaltsverzeichnis |
[Bearbeiten] Eigenschaften der Mersenne-Primzahlen
Es gibt eine Reihe bekannter Eigenschaften der Mersenne-Primzahlen. Um etwa zu untersuchen, ob eine große Zahl eine Primzahl ist, ist die wichtigste wohl die folgende:
- Wenn Mp eine Primzahl ist, dann muss auch p eine Primzahl sein.
Diese Eigenschaft spielt eine wichtige Rolle bei der Suche nach Mersenne-Primzahlen, da man nur noch relativ wenige Kandidaten (nämlich die, bei denen p eine Primzahl ist) testen muss. So kann beispielsweise M10 keine Primzahl sein, da 10 keine Primzahl ist. (In der Tat ist ). Oftmals wird diese Eigenschaft mit ihrer Umkehrung verwechselt und behauptet, dass für jede Primzahl p auch Mp eine Primzahl ist. Das ist aber ein Denkfehler, da z. B. 11 eine Primzahl ist, nicht aber
.
Der Beweis der oben genannten Eigenschaft ergibt sich folgendermaßen: Wenn p=rs zusammengesetzt ist, dann gilt:
- 2rs–1 = (2r – 1) (2r(s–1) + 2r(s–2) + ... + 2r + 1)
und damit ist ein nichttrivialer Faktor von Mp gefunden.
Zwei weitere Eigenschaften von Mersennezahlen sind die folgenden:
- Wenn q ein Teiler von Mp ist, dann gilt q ≡ 1 (mod p) und q ≡ ±1 (mod 8).
- Wenn p eine Primzahl ist und es gilt p ≡ 3 (mod 4), dann gilt:
-
- 2p+1 teilt Mp ⇔ 2p+1 prim
Letztere wurde von Leonhard Euler formuliert, aber erst später von Joseph-Louis Lagrange bewiesen.
Außerdem ist noch bekannt:
- Eine Mersenne-Primzahl kann keine Wieferich-Primzahl sein.
- Unter Annahme der erweiterten Riemannschen Vermutung lässt sich noch zeigen, dass
-
- für x gegen unendlich konvergiert.
Die Mersennezahl Mn ist die Dualzahl, die gerade aus n Einsen besteht. Bei Mersenne-Primzahlen ist also die Anzahl der Einsen selbst eine Primzahl. Zum Beispiel ist 11111 die Dualzahldarstellung von 31.
[Bearbeiten] „Anwendungen“
Neben der Tatsache, dass die größten bekannten Primzahlen Mersenne-Zahlen sind, spielen diese eine wichtige Rolle im Zusammenhang mit vollkommenen Zahlen. 2n - 1(2n - 1) ist immer dann eine vollkommene Zahl, falls 2n − 1 eine Primzahl ist. Jede gerade vollkommene Zahl lässt sich auf diese Weise darstellen. In der Tabelle unten wird die vollkommene Zahl zur n-ten Mersennezahl mit P(n) bezeichnet.
Eine weitere Anwendung ist der Mersenne Twister, ein Pseudozufallszahlengenerator.
[Bearbeiten] Die Suche nach Mersenne-Primzahlen
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 Dualsystem nur aus lauter Einsen bestehen, also, wenn man so will, die binären Schnapszahlen sind.
[Bearbeiten] Der Lucas-Lehmer-Test
Der Lucas-Lehmer-Test ist zum Testen von Mersenne-Zahlen ab M3 geeignet. Er funktioniert wie folgt:
- Sei p ungerade. Ferner sei die rekursive Folge S(k+1) definiert durch S(1) = 4, S(k+1) = S(k)2–2
- Dann gilt: Mp = 2p–1 ist genau dann eine Primzahl, wenn S(p–1) durch Mp teilbar ist.
In dieser von D. N. Lehmer gefundenen Form, die auf Edouard Lucas zurück geht, ist die Anwendung allerdings unpraktisch, weil die Zahlen S(k) sehr schnell sehr groß werden. Deshalb werden heutzutage bereits alle Zwischenschritte modulo M(p) ausgerechnet, so dass große Zahlen vermieden werden:
- Sei S(1) = 4, S(k+1) = S(k)2–2 mod Mp
- Ist S(p–1) = 0 dann ist Mp eine Primzahl.
[Bearbeiten] Beispiele
Wir prüfen mit diesem Verfahren, ob M5 = 25–1 = 31 eine Primzahl ist:
S(1) = 4 S(2) = ( 4² - 2) mod 31 = 14 S(3) = (14² - 2) mod 31 = 8 S(4) = ( 8² - 2) mod 31 = 0
Da S(4) = 0 ist, ist M5 = 31 eine Primzahl.
Wir prüfen mit diesem Verfahren, ob M11 = 211–1 = 2047 = 23 * 89 eine Primzahl ist:
S( 1) = 4 S( 2) = ( 4² - 2) mod 2047 = 14 S( 3) = ( 14² - 2) mod 2047 = 194 S( 4) = ( 194² - 2) mod 2047 = 788 S( 5) = ( 788² - 2) mod 2047 = 701 S( 6) = ( 701² - 2) mod 2047 = 119 S( 7) = ( 119² - 2) mod 2047 = 1877 S( 8) = (1877² - 2) mod 2047 = 240 S( 9) = ( 240² - 2) mod 2047 = 282 S(10) = ( 282² - 2) mod 2047 = 1736
Da S(10) > 0 ist, ist M11 = 2047 keine Primzahl.
Wir prüfen mit diesem Verfahren, ob M19 = 219–1 = 524287 eine Primzahl ist:
S( 1) = 4 S( 2) = ( 4² - 2) mod 524287 = 14 S( 3) = ( 14² - 2) mod 524287 = 194 S( 4) = ( 194² - 2) mod 524287 = 37634 S( 5) = ( 37634² - 2) mod 524287 = 218767 S( 6) = ( 218767² - 2) mod 524287 = 510066 S( 7) = ( 510066² - 2) mod 524287 = 386344 S( 8) = ( 386344² - 2) mod 524287 = 323156 S( 9) = ( 323156² - 2) mod 524287 = 218526 S(10) = ( 218526² - 2) mod 524287 = 504140 S(11) = ( 504140² - 2) mod 524287 = 103469 S(12) = ( 103469² - 2) mod 524287 = 417706 S(13) = ( 417706² - 2) mod 524287 = 307417 S(14) = ( 307417² - 2) mod 524287 = 382989 S(15) = ( 382989² - 2) mod 524287 = 275842 S(16) = ( 275842² - 2) mod 524287 = 85226 S(17) = ( 85226² - 2) mod 524287 = 523263 S(18) = ( 523263² - 2) mod 524287 = 0
Da S(18) = 0 ist, ist M19 = 524287 eine Primzahl (seit 1603 bekannt).
[Bearbeiten] Literatur zum Lucas-Lehmer-Test
- Théorie des Fonctions Numériques Simplement Périodiques, E. Lucas, Amer. Journ. of Math., 1, 289–
- An extended theory of Lucas' functions, D. H. Lehmer, Annals of mathematics, 31, 419–
[Bearbeiten] Suche nach Mersenne-Primzahlen: GIMPS
Bisher kennt man 44 Mersenne-Primzahlen. Mit Computerhilfe versucht man, weitere Mersenne-Primzahlen zu finden. Da es sich um sehr große Zahlen handelt – die 44. Mersenne-Primzahl hat mehr als neun Millionen Ziffern im Dezimalsystem – sind die Berechnungen aufwändig. Rechenoperationen mit derart großen Zahlen werden von Computern nicht von Haus aus unterstützt. Man muss die Zahlen in großen Feldern abspeichern und die damit erforderlichen Grundrechenarten programmieren. Dies führt zu 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 (Prime95) 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.
[Bearbeiten] Vermutungen zu den Mersenne-Zahlen
- Gibt es unendlich viele Mersenne-Primzahlen? Man vermutet aufgrund von plausiblen Heuristiken, dass es etwa
viele Mersenne-Primzahlen Mp gibt mit p < x. Wenn dies der Fall ist, so gibt es tatsächlich unendlich viele Mersenne-Primzahlen.
- Gibt es unendlich viele Mersenne-Zahlen Mp mit p prim, die keine Primzahlen sind? Auch hier vermutet man als Antwort ja. Dies würde zum Beispiel aus der Vermutung, dass es unendlich viele Sophie-Germain-Primzahlen gibt, die kongruent 3 modulo 4 sind, folgen.
- Sind alle Mersenne-Zahlen Mp mit p prim quadratfrei, d. h. kommt in der Primfaktorzerlegung der Zahl jeder Primfaktor genau einmal vor? Man konnte bisher noch nicht einmal beweisen, dass dies für unendlich viele Mersenne-Zahlen gilt.
- Gilt die "neue Mersenne-Vermutung"? Die Folge von Mersenne-Primzahlen, die Mersenne angab, lässt vermuten, dass er meinte, dass eine Mersenne-Zahl Mp mit p prim genau dann prim ist, wenn p=2k±1 oder p=4k±3. Da diese Aussage nicht gilt, stellten P. Bateman, J.Selfridge und S.Wagstaff die neue Mersenne-Vermutung auf.
- Diese besagt, dass aus zwei der folgenden drei Aussagen bereits die dritte folgt:
- n = 2k ± 1 oder n = 4k ± 3
- 2n – 1 ist eine (Mersenne) Primzahl
- (2n+1)/3 ist eine Primzahl
- Sind alle Glieder der Folge C(0) = 2, C(k+1) = 2C(k)–1 Primzahlen? Die stärkere Vermutung, dass alle Zahlen MMp Primzahlen sind, für die Mp eine Primzahl ist, konnte inzwischen für p=13 widerlegt werden. Diese letzteren Zahlen nennt man doppelte Mersenne-Zahlen. Auch hier ist noch nicht bekannt, ob es unendlich viele Primzahlen darunter gibt.
[Bearbeiten] 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 = 23 * 89 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 glaubt er dies auch für n = 23, 29, 31 und 37 (ist nur für n = 31 korrekt). |
1640 | Fermat widerlegt Cataldi für n = 23 und n = 37: 223–1 = 47 * 178481 und 237–1 = 223 * 616318177 sind 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: 229-1 =233 * 1103 * 2089 |
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 M(n) für n = 2,3,5,7,13,17,19,31,61,89,107 und 127. |
1951 | Beginn des Einsatzes von Computern, die Länge der größten bekannten Primzahl steigt bis 1952 von 39 Stellen auf 687 Dezimalstellen. |
1963 | Gillies entdeckt M(11.213) mit 3.376 Stellen. |
1996 | Joel Armengaud und George Woltman entdecken mit GIMPS M(1.398.269) mit 420.921 Stellen. |
1999 | Mit M(6.972.593), die 2.098.960 Stellen hat, kennt man erstmals eine Primzahl mit mehr als 1 Million Stellen. |
2004 | Es wird nachgewiesen, dass M(24.036.583), eine Zahl mit 7.235.733 Stellen, prim ist. |
2005 | Im Februar wird vom GIMPS-Projekt die 42. Mersenne-Primzahl entdeckt: M(25.964.951) hat 7.816.230 Stellen.
Ebenfalls vom GIMPS-Projekt wird im Dezember die 43. Mersenne-Primzahl entdeckt: M(30.402.457) hat 9.152.052 Stellen. |
2006 | Am 4. September vermeldet das GIMPS-Projekt die Entdeckung der 44. Mersenne-Primzahl M(32.582.657) mit 9.808.358 Stellen. |
[Bearbeiten] Liste aller bekannten Mersenne-Primzahlen
Nr. | n | Anzahl Ziffern von M(n) |
Anzahl Ziffern der perfekten Zahl P(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 | 1.257.787 | 378632 | 757263 | 1996 | David Slowinski + Gage |
35 | 1.398.269 | 420921 | 841842 | 1996 | Joel Armengaud + George Woltman + GIMPS |
36 | 2.976.221 | 895932 | 1.791.864 | 1997 | Gordon Spence + George Woltman + GIMPS |
37 | 3.021.377 | 909526 | 1.819.050 | 1998 | Roland Clarkson + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
38 | 6.972.593 | 2.098.960 | 4.197.919 | 1999 | Nayan Hajratwala + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
39 | 13.466.917 | 4.053.946 | 8.107.892 | 2001 | Michael Cameron + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
40? | 20.996.011 | 6.320.430 | 12.640.859 | 2003 | Michael Shafer + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
41? | 24.036.583 | 7.235.733 | 14.471.466 | 2004 | Josh Findley + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
42? | 25.964.951 | 7.816.230 | 15.632.458 | 2005 | Martin Nowak + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
43? | 30.402.457 | 9.152.052 | 18.304.103 | 2005 | Curtis Cooper + Steven Boone + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
44? | 32.582.657 | 9.808.358 | 19.616.714 | 2006 | Curtis Cooper + Steven Boone + George Woltman + Scott Kurowski + GIMPS, PrimeNet |
Bisher (Stand 28. November 2006) ist unbekannt, ob es zwischen n=13.466.917 und n=32.582.657 neben den vier bekannten Mersenne-Primzahlen noch weitere gibt.
[Bearbeiten] Weblinks
Wiktionary: Mersenne-Primzahl – Bedeutungserklärungen, Wortherkunft, Synonyme und Übersetzungen |
- prime Mersenne Numbers - History, Theorems and Lists (engl.)
- Great Internet Mersenne Prime Search (GIMPS) mit Sitz in Orlando, Florida
- Die Deutsche Great Internet Mersenne Prime Search (GIMPS) Homepage
- prime Mersenne Numbers - History, Theorems and Lists Explanation (engl.)
- Mersenne Primzahlen Bibliografie mit Links auf die Original-Veröffentlichungen (engl.)
- Wie eine neue Mersenne Primzahl entdeckt wurde - dpa-Hintergrundbericht
- prime Mersenne numbers - Wolframresearch/Mathematica (engl.)
- Mq = (8x)^2 - (3qy)^2 Mersenne Proof (.pdf)
- Mq = x^2 + d.y^2 Math Thesis (.pdf)
- Die 43te Mersenne-Primzahl in dezimaler Darstellung (Hinweis: Die Datei ist ca. 9 MB groß)
- mprint5 - schnelle Berechnung der Mersenne-Primzahlen von dem Finnen Mikko Tommila