Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 23. Januar 2020 

Mersenne-Primzahl


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Eine Mersenne-Primzahl ist eine Primzahl die eins weniger als die Zweierpotenz Primzahl ist. Beispielsweise ist 3 = 2 2 -1 eine Mersenne-Primzahl genau wie 7 = 3 -1. Der kleinste prime Exponent der auf Mersenne-Primzahl führt ist 11 : 2 11 -1=2047 ist faktorisierbar als 2047 = 23 89.

Allgemeiner nennt man die Zahl M p :=2 p -1 die p te Mersenne-Zahl . Mit dieser Bezeichnungsweise sind die Mersenne-Primzahlen die Mersenne-Zahlen die Primzahlen sind.

Den Namen haben diese Primzahlen von französischen Mönch und Priester Marin Mersenne (1588 1648) der behauptete dass für p = 2 3 5 7 13 19 31 67 127 und 257 M p eine Primzahl ist. Dabei irrte er bei den Zahlen 67 und 257 und die Zahlen 61 89 und 107. Daß M 67 keine Primzahl ist wurde erst im 1903 vom Mathematiker Cole entdeckt. Um den zu führen daß M 257 keine Primzahl ist wurde 1932 eine Rechenmaschine verwendet.
Bei der Zahl 67 handelt es möglicherweise um einen Lesefehler seitens Mersenne aus Korrespondenz mit Frenicle de Bessy und Fermat wobei er p =61 verwechselte mit p =67.

Inhaltsverzeichnis

Eigenschaften der Mersenne-Primzahlen

Es gibt eine Reihe von bekannten der Mersenne-Primzahlen. Um etwa zu untersuchen ob große Zahl eine Primzahl ist ist die wohl die folgende:

Wenn M p eine Primzahl ist dann muss auch p eine Primzahl sein.

Diese Eigenschaft spielt eine wichtige Rolle der Suche nach Mersenne-Primzahlen da man nur sehr wenige Kandidaten (nämlich die bei denen p eine Primzahl ist) testen muss.

Beispiel: Die Zahl M 10 kann keine Primzahl sein da 10 Primzahl ist. (In der Tat ist M 10 = 2 10 -1 = 1023 = 3·11·31.)

Oftmal wird diese Eigenschaft mit deren (wenn p eine Primzahl ist dann ist auch M p eine Primzahl) verwechselt. Da macht man einen Denkfehler da z.B. 11 eine Primzahl nicht aber M 11 = 2 11 -1 = 2047 = 23·89.

            
Expertenabschnitt: Dieser Abschnitt enthält tiefergehende Informationen für die Teil zusätzliches Fachwissen notwendig ist.

Der Beweis der oben genannten Eigenschaft sich folgendermaßen: Wenn p = rs zusammengesetzt ist dann gilt:

2 rs -1 = (2 r - 1) (2 r ( s -1) + 2 r ( s -2) + ... + 2 r + 1)
und damit ist ein nichttrivialer Faktor M p gefunden.

Zwei weitere Eigenschaften von Mersennezahlen sind folgenden:

  • Wenn q ein Teiler von M p 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:
2 p +1 teilt M p     <=>     2 p +1 prim

Letztere wurde von Euler formuliert aber später von Lagrange bewiesen.

Außerdem ist noch bekannt:

<math>\sum_{p<x q|M_p}\frac{1}{q}</math>
für x gegen unendlich konvergiert.

            

Anwendungen

Neben der Tatsache dass die größten Primzahlen Mersenne-Zahlen sind spielen diese eine wichtige im Zusammenhang mit perfekten Zahlen. Dies wird 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 Zahlen für die Suche nach Primzahlrekorden. Der basiert ganz wesentlich darauf dass die Mersenne-Zahlen Binärsystem nur aus lauter Einsen bestehen also man so will die binären Schnapszahlen sind.

Der Lucas-Lehmer-Test

Der Lucas-Lehmer-Test 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: M p = 2 p -1 ist genau dann eine Primzahl wenn S ( p -1) durch M p teilbar ist.

In dieser von D. H. Lehmer Form die auf E. Lucas zurück geht die Anwendung allerdings unpraktisch weil die Zahlen S ( k )) sehr schnell sehr groß werden. Deshalb heutzutage das Verfahren dahingehend abgewandelt dass bereits Zwischenschritte modulo M ( p ) ausgerechnet werden und damit derart große vermieden werden:

Sei S (1) = 4 S ( k +1) = S ( k ) 2 -2 mod M p
Ist S ( p -1)=0 dann ist M p eine Primzahl.

Beispiel

Wir prüfen mit diesem Verfahren ob M 5 = 2 5 -1 = 31 eine Primzahl ist.

  S (1) = 4  S (2) = 4 2  - 2 mod 31 = 14 31 = 14  S (3) = 14 2  - 2 mod 31 = 194 31 = 8  S (4) = 8 2  - 2 mod 31 = 62 31 = 0  

Da S (4) = 0 ist ist M 5 = 31 also eine Primzahl.

Literatur zum Lucas-Lehmer-Test

  • Théorie des Fonctions Numériques Simplement Périodiques E. Lucas Amer. Journ. of Math. 289-
  • An extended theory of Lucas' functions D. H. Lehmer Annals of mathematics 419-

Suche nach Mersenne-Primzahlen: GIMPS

Bisher kennt man 40 Mersenne-Primzahlen. Mit versucht man weitere Mersenne-Primzahlen zu finden.

Da es sich um sehr große handelt - die 40. Mersenne-Primzahl ist mehrere Ziffern lang - sind die Berechnungen sehr Rechenoperationen mit derart großen Zahlen werden von nicht von Hause aus unterstützt. Man muss Zahlen in großen Feldern abspeichern und die erforderlichen Grundrechenarten programmieren. Dies führt zu sehr Programmlaufzeiten.

GIMPS ( G reat I nternet M ersenne P rime S earch) versucht daher weltweit möglichst viele Computer den Berechnungen zu beteiligen und stellt die Software für eine Reihe von Plattformen (Windows Linux ...) zur Verfügung. Jeder kann mitmachen er einen Rechner mit (zeitweise) freien CPU-Kapazitäten Dazu muss man sich von der Website Software herunterladen und dann installieren. Danach meldet sich bei GIMPS und lässt sich eine geben die man untersuchen soll. Wenn die erledigt sind (meist nach mehreren Wochen oder meldet man das Ergebnis bei GIMPS zurück.

Vermutungen zu den Mersenne-Zahlen

  • Gibt es unendlich viele Mersenne-Primzahlen? (Man aufgrund von plausiblen Heuristiken dass es etwa \cdot \ln x</math> viele Mersenne-Primzahlen <math>M_p</math> gibt <math>p < x</math>. Wenn dies der Fall so gibt es tatsächlich unendlich viele Mersenne-Primzahlen)

  • Gibt es unendlich viele Mersenne-Zahlen <math>M_p</math> p prim die keine Primzahlen sind? (Auch vermutet man ja. Dies würde zum Beispiel der Vermutung dass es unendlich viele Sophie-Germain-Primzahlen gibt die kongruent 3 modulo 4 folgen.)

  • Sind alle Mersenne-Zahlen M p mit p prim quadratfrei d.h. in der Primfaktorzerlegung der Zahl kommt jede Primzahl nur einmal vor? (Man konnte bisher noch nicht beweisen dass dies für unendlich viele Mersenne-Zahlen

  • Gilt die "neue Mersenne-Vermutung"? (Die Folge Mersenne-Primzahlen die Mersenne angab lässt vermuten dass meinte dass eine Mersenne-Zahl M p mit p prim genau dann prim ist wenn p =2 k ±1 oder p =4 k ±3. Da diese Aussage nicht gilt stellten Bateman J.Selfridge und S.Wagstaff die neue Mersenne-Vermutung

Diese besagt dass aus zwei der folgenden Aussagen bereits die dritte folgt:
  1. n = 2 k ± 1 oder n = 4 k ± 3
  2. 2 n - 1 ist eine (Mersenne) Primzahl
  3. (2 n +1)/3 ist eine Primzahl

  • Sind alle Glieder der Folge C (0) = 2 C ( k +1) = 2 C ( k ) -1 Primzahlen? (Die stärkere Vermutung dass alle M M p Primzahlen sind für die M p eine Primzahl ist konnte inzwischen für p =13 widerlegt werden. Diese letztere Zahlen nennt doppelte Mersenne-Zahlen. Auch hier ist noch nicht ob es unendlich viele Primzahlen darunter gibt.)

  • Sei p eine Primzahl und 2 p -1 kein Vielfaches einer Quadratzahl. Gibt es Primzahl q mit der Eigenschaft 2 p -1 = 0 (mod q 2 )?

Weblinks

Geschichte der Mersenne-Primzahlen als Tabelle

Jahr Ereignis
bis 1536 Man glaubt dass für alle Primzahlen p 2 p -1 sei prim.
1536 Hudalricus Regius zeigt dass 2 11 -1 keine Primzahl ist obwohl 11 prim
1603 Pietro Cataldi (1548 - 1626) zeigt dass n -1 Primzahlen sind für n=17 19. Fälschlicherweise er dies auch für n=23 29 31 (ist nur für n=31 korrekt)
1640 Fermat widerlegte Cataldi für n=23 und n=37: 23 -1 und 2 37 -1 sind doch keine Primzahlen.
1644 Mersenne behauptet 2 n - 1 sei prim für n 2 3 5 7 13 17 19 67 127 und 257 jedoch nicht prim alle anderen natürlichen Zahlen kleiner als 257 zu seinem Werk "Cogitata Physica-Mathematica"). Dies ist falsch denn 2 n -1 ist prim sowohl für n=61 (was bemerkt wird) als auch für n=89 107 erst nach 1900 nachgewiesen)
1738 Euler widerlegt Cataldi für n=29.
1750 Euler bestätigt dass Cataldi für n=31 richtig 2 31 - 1 ist prim.
1870 Edouard Lucas (1842 - 1891) formuliert die theoretischen für den Lucas-Lehmer Test.
1876 Lucas bestätigt Mersenne: 2 127 -1 ist prim.
1883 M. Pervouchine (orthodoxer Priester in Perm/Russland) zeigt 2 61 -1 prim ist (Widerspruch zu Mersenne).
1911 R.E. Powers widerspricht Mersenne für n=89: 2 n -1 ist prim.
1914 Powers widerspricht Mersenne auch für n=107: 2 n -1 ist prim. Fast gleichzeitig kommt auch Fauquembergue zu dieser Aussage
1930 Lehmer (1867-1938) formuliert den Lucas-Lehmer Test.
1932 Lehmer zeigt: M(149) und M(257) sind nicht
1934 Powers zeigt: M(241) ist nicht prim.
1944 H.S.Uhler zeigt: M(157) und M(167) sind nicht
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 überprüft. Man kennt nun die Mersenne-Primzahlen für 3 5 7 13 17 19 31 89 107 und 127.
1951 Beginn des Einsatzes von Computern
1999 Mit M(6972593) kennt man erstmals eine Primzahl mehr als 1 Million Stellen.
17. November 2003 M(20996011) wird gefunden die bis jetzt (Dezember 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 13.11.1996 Joel Armengaud + George Woltman + GIMPS
36 2976221 895932 1791864 24.8.1997 Gordon Spence + George Woltman + GIMPS
37 3021377 909526 1819050 27.1.1998 Roland Clarkson + George Woltman + Scott + GIMPS PrimeNet
38 6972593 2098960 4197919 1.6.1999 Nayan Hajratwala + George Woltman + Scott + GIMPS PrimeNet
? 13466917 4053946 8107892 14.11.2001 Michael Cameron + George Woltman + Scott + GIMPS PrimeNet
? 20996011 6320430 12640859 17.11.2003 Michael Shafer + George Woltman + Scott + GIMPS PrimeNet



Bücher zum Thema Mersenne-Primzahl

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Mersenne-Zahl.html">Mersenne-Primzahl </a>