Wikipedia

Mersenne-Zahl

Zahl der Form (2^n)−1
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 1. Januar 2006 um 12:04 Uhr durch Löschfix (Diskussion | Beiträge) (→Weblinks). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Eine Mersenne-Primzahl ist eine Primzahl der Form 2p–1 wobei p eine 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. 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 verwechselte mit p=67.

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 sehr wenige Kandidaten (nämlich die bei denen p eine Primzahl ist) testen muss.

Beispiel: Die Zahl M10 kann keine Primzahl sein, da 10 keine Primzahl ist. (In der Tat ist M10 = 210–1 = 1023 = 3·11·31.)

Oftmals wird diese Eigenschaft mit deren Umkehrung (wenn p eine Primzahl ist, dann ist auch Mp eine Primzahl) verwechselt. Da macht man aber einen Denkfehler, da z. B. 11 eine Primzahl ist, nicht aber M11 = 211–1 = 2047 = 23·89.

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:

 
für x gegen unendlich konvergiert.

Anwendungen

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.

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.

Der Lucas-Lehmer-Test

Der Lucas-Lehmer-Test ist zum Test von Mersenne-Zahlen ab M3 geeignet. Er funktioniert wie folgt:

Sei p ungerade. Ferner sei die Funktion S(k) 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.

Beispiele

Wir prüfen mit diesem Verfahren, ob M5 = 25–1 = 31 eine Primzahl ist: 

Test für M5 = 2^5-1 = 31 = 31
 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: 

Test für M11 = 2^11-1 = 2047 = 23 * 89
 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: 

Test für M19 = 2^19-1 = 524287 = 524287
 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).

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–

Suche nach Mersenne-Primzahlen: GIMPS

Bisher kennt man 43 Mersenne-Primzahlen. Mit Computerhilfe versucht man, weitere Mersenne-Primzahlen zu finden. Da es sich um sehr große Zahlen handelt – die 43. Mersenne-Primzahl hat mehr als neun Millionen Ziffern – sind die Berechnungen sehr aufwendig. 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.

Vermutungen zu den Mersenne-Zahlen

  • Gibt es unendlich viele Mersenne-Primzahlen? (Man vermutet aufgrund von plausiblen Heuristiken, dass es etwa   viele Mersenne-Primzahlen   gibt mit  . Wenn dies der Fall ist, so gibt es tatsächlich unendlich viele Mersenne-Primzahlen)
  • Gibt es unendlich viele Mersenne-Zahlen   mit p prim, die keine Primzahlen sind? (Auch hier vermutet man 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:
  1. n = 2k ± 1 oder n = 4k ± 3
  2. 2n – 1 ist eine (Mersenne) Primzahl
  3. (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 letztere Zahlen nennt man doppelte Mersenne-Zahlen. Auch hier ist noch nicht bekannt, ob es unendlich viele Primzahlen darunter gibt.)
  • Sei p eine Primzahl und 2p–1 kein Vielfaches einer Quadratzahl. Gibt es eine Primzahl q mit der Eigenschaft 2p–1 = 0 (mod q2)?


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 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 = 47 * 178481 und 237–1 = 223 * 616318177 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: 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 für n = 2,3,5,7,13,17,19,31,61,89,107 und 127.
1951 Beginn des Einsatzes von Computern, die größte bekannte Primzahl steigt bis 1952 von 39 Stellen auf 687 Dezimalstellen.
1963 Gillies entdeckt M(11213) mit 3376 Stellen.
1996 Joel Armengaud und George Woltman entdecken mit GIMPS M(1398269) mit 420921 Stellen. Die Jagd beginnt.
Innerhalb der nächsten 8 Jahre soll sich die Anzahl der Stellen der größten bekannten Mersenne-Primzahl um den Faktor 17 erhöhen.
1999 Mit M(6972593), die 2.098.960 Stellen hat, kennt man erstmals eine Primzahl mit mehr als 1 Million Stellen.
2004 Es wird nachgewiesen, dass M(24036583), eine Zahl mit 7.235.733 Stellen, prim ist.
2005 Im Februar wurde vom GIMPS-Projekt die 42. Mersenne-Primzahl entdeckt: 225.964.951 -1 hat 7.816.230 Stellen.

Ebenfalls vom GIMPS-Projekt wurde im Dezember die 43. Mersenne-Primzahl entdeckt: 230.402.457 -1 hat 9.152.052 Stellen.

Liste aller bekannten Mersenne-Primzahlen

Nr. n Anzahl
Ziffern
von M(n) 		Anzahl
Ziffern der
perfekten
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 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

Bisher (Stand 26.12.05) ist unbekannt, ob es zwischen der 38sten und der 43sten bekannten Mersenne-Primzahl noch weitere gibt.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Mersenne-Zahl&oldid=12152119“