Mersenne-Primzahlen


In der Antike und bis ins Mittelalter glaubte man, daß für jede Primzahl p die Zahl 2p-1 wieder eine Primzahl ist. Dabei ist klar, daß 2k-1 für eine zusammengesetzte Zahl k=mn wegen

2k-1=(2m-1)(2(n-1)m+2(n-2)m +...+2m+1)

keine Primzahl sein kann. So wurde etwa 1456 von einem unbekannten Mathematiker die Primzahleigenschaft von 213-1 bewiesen. Daher war man erstaunt, als 1536 Hudalricus Regius die Zerlegung von 211-1=2047=23*89 fand. Im Jahre 1603 hatte Pietro Cataldi bewiesen, daß auch 217-1 und 219-1 Primzahlen sind, und dann behauptet, daß dies auch für die Exponenten p=23, 29, 31 und 37 zuträfe. Pierre Fermat zeigte 1640 jedoch, daß diese Behauptung für p=23 und 37 falsch ist und Leonhard Euler zeigte 1738 dasselbe für p=29, konnte allerdings 1750 wirklich beweisen, daß 231-1 eine Primzahl ist.

Im Jahre 1644 behauptete nun der französische Mönch Marin Mersenne im Vorwort seiner Cogitata Physica-Mathematica, daß für alle Primzahlen bis 257 nur die Fälle

p=2,3,5,7,13,17,19,31,67,127, 257

eine Primzahl 2p-1 lieferten.

Wenn man etwa die Größe der Primzahl (1876 von Lucas bewiesen)

2127-1=170141183460469231731687303715884105727

bedenkt, so dürfte klar sein, daß Mersenne zu seiner Zeit unmöglich für alle Primzahlen p bis 257 die Primzahleigenschaft von 2p-1 wirklich überprüft haben kann. So irrte er auch in den Fällen p=67 und 257. Außerdem bewies Pervouchine 1883, daß Mersenne den Fall p=61 übersehen hatte und Powers zeigte dasselbe 1911 für p=89 und 1914 für p=107. Trotzdem nennt man die Zahlen Mn=2n-1 heute Mersennesche Zahlen und insbesondere Mersennesche Primzahlen, wenn sie tatsächlich prim sind. Erst 1947 hatte man für alle Primzahlen p bis 257 wirklich überprüft, welche von ihnen Mersennsche Primzahlen liefern. Es sind dies

p=2,3,5,7,13,17,19,31,61, 89,107,127.

Warum ausgerechnet Mersennesche Primzahlen?

Daß bei der Rekordjagd nach immer größeren Primzahlen mittels Computer die Mersenneschen Primzahlen eine so bedeutende Rolle spielen, hat verschiedene Gründe. Zum einen ist wegen der Binärdarstellung 111....111 (p Einsen) der Zahl 2p-1 dies gerade die größte Zahl, die man in einem Computer mit dieser Stellenzahl darstellen kann, zum anderen kennt man aber auch einige theoretische Aussagen über Mersennesche Primzahlen. Dies kann den Test auf die Primzahleigenschaft gegenüber beliebigen natürlichen Zahlen erheblich abkürzen. So gilt etwa der folgende Satz von Lucas, auf dem der sogenannte Lucas-Lehmer-Test beruht.

Satz: Für eine ungerade Primzahl p ist Mp genau dann eine Primzahl, wenn sie die Lucas-Zahl Lp-1 teilt.

Dabei sind die Lucas-Zahlen rekursiv durch L1=4 und Ln+1=Ln2-2 definiert.

Welche Mersenneschen Primzahlen sind zur Zeit bekannt?

In der folgenden Tabelle sind in fortlaufender Numerierung die Mersenneschen Primzahlen Mp durch ihre erzeugende Primzahl p angegeben. Zusätzlich findet man weitere Informationen über Mp.

Falls schon aktuellere Mersenne-Zahlen bekannt sind, ist das unter folgender Adresse nachzulesen:

http://www.utm.edu/research/primes/mersenne.shtml

Nr. p Dezimalstellen von Mp Entdeckungsjahr Entdecker
1 2 1 - -
2 3 1 - -
3 5 2 - -
4 7 3 - -
5 13 4 1456 unbekannt
6 17 6 1588 Cataldi
7 19 6 1588 Cataldi
8 31 10 1772 Euler
9 61 19 1883 Pervushin
10 89 27 1911 Powers
11 107 33 1914 Powers
12 127 39 1876 Lucas
13 521 157 1952 Lehmer & Robinson
14 607 183 1952 Lehmer & Robinson
15 1279 386 1952 Lehmer & Robinson
16 2203 664 1952 Lehmer & Robinson
17 2281 687 1952 Lehmer & Robinson
18 3217 969 1957 Riesel
19 4253 1281 1961 Hurwitz & Selfridge
20 4423 1332 1961 Hurwitz & Selfridge
21 9689 2917 1963 Gillies
22 9941 2993 1963 Gillies
23 11213 3376 1963 Gillies
24 19937 6002 1971 Tuckerman
25 21701 6533 1978 Noll & Nickel
26 23209 6987 1979 Noll
27 44497 13395 1979 Nelson & Slowinski
28 86243 25962 1982 Slowinski
29 110503 33265 1988 Colquitt & Welsh
30 132049 39751 1983 Slowinski
31 216091 65050 1985 Slowinski
32 756839 227832 1992 Slowinski & Gage
33 859433 258716 1994 Slowinski & Gage
34 1257787 378632 1996 Slowinski & Gage
35 1398269 420921 1996 Armengaud et al.
36 2976221 895932 1997 Spence et al.
37 3021377 909526 1998 Clarkson et al.
38 6972593 2098960 1999 Hajratwala et al.
39 13466917 4053946 2001 Cameron et al.
40 20996011 6320430 2003 Shafer et al.
41 24036583 7235733 2004 Findley et al.
42 25964951 7816230 2005 Nowak et al.
43 30402457 9152052 2005 Cooper & Boone
44 32582657 9808358 2006 Cooper & Boone
45 37156867 11185272 2008 Elvenich
46 42643801 12837064 2009 Strindmo
47 43112609 12978189 2008 Smith
48 57885161 17425170 2013 Cooper
49 74207281 22338618 2016 Cooper