Kap 1.1
Vollkommene Zahlen
und Mersenne-Zahlen

Auf einem Sonderstempel der US-Post im Staat Illinois aus dem Jahre 1968 ist die bemerkenswerte Meldung zu lesen: 2¹¹²¹³-1 is prim!
Warum hält die amerikanische Post wohl diese Meldung für so wichtig, dass man ihr einen Sonderstempel widmet? Wir werden uns im Folgenden genauer mit Zahlen der Form 2ⁿ-1 beschäftigen.
Wie wir beim Beweis von 1.8f gesehen haben, ist eine Zahl z immer schon dann vollkommen, wenn sie von der Form z=2^n-1(2ⁿ-1) ist, wobei der zweite Faktor 2ⁿ-1 prim sein muß. (Also schon wieder diese Zahlen der Form 2ⁿ-1!) Überprüfen wir das zunächst einmal an einigen kleinen Beispielen:

AUFGABE 1.38
Bestätige die Angaben über die Vollkommenheit der Zahlen. Setze dann die Tabelle bis n=20 fort. (Benutze eventuell ein Programm zu Primfaktorzerlegung.)

Welche Regelmäßigkeit steckt in dieser Tabelle? Da die Zahlen der Form 2ⁿ-1 auch an anderer Stelle eine Rolle spielen, wollen wir uns erst mal diesen zuwenden.

DEFINITION
M_n:=2ⁿ-1 heißt n-te Mersenne-Zahl.
(nach dem französischen Jesuitenpater Marin Mersenne (1588-1648), der die Bedeutung dieser Zahlen als Erster erkannt hat und etliche (auch falsche) Behauptungen über sie aufgestellt hat)

Manche dieser M_n sind prim, andere wiederum nicht. Wie kann man schnell erkennen, für welchen Index n M_n prim ist? Die ersten Beispiele lassen vermuten, daß M_n prim ist, wenn nur n prim ist. Spätestens ab n=11 widerlegt sich diese Behauptung von selbst. Allerdings gilt der

SATZ 1
Ist M_n prim, so ist auch n prim.

Beweis: Wir zeigen die Kontraposition: n nicht prim Þ M_n nicht prim
Ist nämlich n=k× l (k,l>1), so folgt M_n=2^{k× l}-1=(2^k)^l-(1^k)^l=(2^k-1)× Rest nach (F1)

Damit haben wir gleichzeitig ein zweites Ergebnis: M_k teilt M_{k× l} oder in anderen Worten: Jede zweite Mersenne-Zahl ist durch 3=M₂ teilbar, jede dritte durch 7=M₃, jede fünfte durch 31=M₅ usw. Das macht das Faktorisieren von Mersenne-Zahlen wesentlich einfacher: will man z.B. M₃₀=2³⁰-1=1.073.741.823 faktorisieren, so weiß man wegen 2ï 30 und 3ï 30 und 5ï 30, daß M₃₀ mindestens durch 3, 7 und 31 teilbar ist; tatsächlich gilt: M₃₀=3^2× 7× 11× 31× 151× 331.

AUFGABE 1.39
a) Zerlege M₂₀, M₂₁ und M₂₈ in Primfaktoren.
b) Schreibe ein Programm, daß die Primfaktorzerlegungen aller Mersenne-Zahlen bis n=30 ausgibt.

AUFGABE 1.40
Untersuche die Zahlen m_n:=2ⁿ+1 für n£ 30 mit einem geeigneten Programm auf Zerlegbarkeit. Was fällt auf?

AUFGABE 1.41
Beweise: (1) n ungerade Þ3ï m_n
(2) m_n prim Þ n=2^k, kÎN
(3) M_n=M_k×m_k mit k=n/2

AUFGABE 1.42
Benutze c), um M_n für n=32, 34, 36, 38 und 40 zu zerlegen.
Wie viele Stellen hat M₆₀? Gib die Primfaktorzerlegung von M₆₀ an.

Schaut man sich die Tabelle der Primfaktorzerlegungen der ersten 30 Mersenne-Zahlen an, so drängt sich die Vermutung auf, daß für p>2 gilt: pï M_p-1. Diese Vermutung ist richtig, und wir werden sie später beweisen (kleiner Fermatscher Satz).

Damit haben wir die Frage, welche der M_n prim sind, noch nicht befriedigend beantwortet. Wir werden dies auch nicht können, da dies bis heute eine unbeantwortete Frage der Mathematik ist. Man hat bis heute (1994) genau 30 solcher Mersenne-Primzahlen gefunden - die größte davon hat mehr als 65.000 Ziffern (siehe weiter unten). Die Mersenne-Zahlen eignen sich für Untersuchungen über Zusammensetzbarkeit mit Computern besonders gut . Das liegt unter anderem daran, das sie in der Binärdarstellung aus lauter Einsen bestehen. Mersenne selbst hielt sowohl M₆₇ als auch M₁₂₇ für prim und konnte wohl in seinen kühnsten Träumen nicht erahnen, daß es jemals möglich sein würden, dies zu überprüfen. Tatsächlich zeigte 1876 Edouard Lucas (ein Name, der uns noch häufiger begegnen wird), daß M₆₇ nicht prim ist, ohne allerdings einen der Primfaktoren angeben zu können, was erst 1903 dem Amerikaner Cole gelang, der in einem der merkwürdigsten Vorträge, der je auf einer wissenschaftlichen Tagung gehalten wurde, auf einer Tafelhälfte zunächst 2⁶⁷-1 und danach auf der zweiten Tafelhälfte das Produkt von 193.707.721 und 761.838.257.287 berechnete. Die beiden Ergebnisse stimmten überein. Ohne ein weiteres Wort setzte sich Cole unter dem Applaus der Anwesenden. Ergänzend sei erwähnt, daß die beiden Faktoren prim sind.

Ebenfalls 1876 zeigte Lucas, daß M₁₂₇ tatsächlich prim ist. Diese Zahl - ausgeschrieben 170.141.183.460.469.231.731.687.303.715.884.105.727 - hielt bis 1952 den Weltrekord, als mit den damals noch neuen Computern M₅₂₁ (eine Zahl mit 159 Stellen) als prim nachgewiesen wurde. Über die Verfahren, die Lucas und seine Nachfolger benutzten, werden wir in einem späteren Kapitel noch mehr hören.
Hier sei zunächst nur kurz das von Lucas erdachte und benutzte Verfahren vorgestellt:

Man bilde nach der Rekursionsvorschrift x₁=4 und x_n+1=x_n²-2 die sogenannte Lucasfolge: 4, 14, 194, 37634..... M_n ist genau dann prim, wenn M_n Teiler von x_n-1 ist.

z.B.: M₃=7ï 14 - M₄=15 teilt nicht 194 - M₅=31ï 37634
Der Nachteil des Verfahrens liegt darin, daß die Testzahlen schnell sehr viel größer als die eigentlich zu untersuchenden Mersenne-Zahlen sind. In den folgenden Jahren wurden deshalb sehr viel effizientere Verfahren entwickelt.

Der amerikanische Mathematiker Lehmer veränderte das Verfahren insofern, als er in der Lucasfolge nur noch die Reste der Folgeglieder bezüglich M_n betrachtete. (Lucas-Lehmer-Test). Wir werden in einem späteren Kapitel darauf zurückkommen.

Kommen wir nun zu den vollkommenen Zahlen. Mit den neu gewonnenen Begriffen können wir nun die im Beweis von 1.8f gewonnen Erkenntnisse so formulieren:

SATZ von EUKLID
Ist M_n eine Mersenne-Primzahl, so ist z=2^n-1× M_n vollkommen.
Beweis: s (z)=

Die Umkehrung dieses Satzes bewies Euler, allerdings unter der Voraussetzung, dass z gerade ist. Die Frage, ob es auch ungerade vollkommene Zahlen gibt, ist bis heute ungeklärt.

SATZ von EULER
Ist z vollkommen und gerade, dann ist z=2^n-1× M_n mit M_n prim.
Beweis: Es sei als z vollkommen und gerade. Dann ist z=2^n-1× b, wobei b ungerade ist. Es sei s (b)=B. Da z vollkommen ist, gilt s (z)=2z. Also
2z=s(z)=s (2^n-1×b)=s (2^n-1)× s (b)=(2ⁿ-1)B
Þ b:B= (*)
Die rechte Seite des Bruchs ist vollständig gekürzt. Dann muß b Vielfaches von 2ⁿ-1 sein; es sei z.B. b=c(2ⁿ-1); cÎ N ;

1. Fall c>1: Wegen b=c(2ⁿ-1) hat b mindestens die Teiler 1, 2ⁿ-1, c und b. Es gilt also s (b)=B³ b+2ⁿ-1+c+1 und damit:


Dies ist ein Widerspruch zur Aussage (*). Also muß c=1 sein!

2.Fall c=1: Es ist also b=2ⁿ-1. Dann gilt mit (*): B=2ⁿ=b+1=s (b). Die Gleichung s (x)=x+1 ist aber nur für primes x erfüllt. Also ist
b=2ⁿ-1=M_n prim, was zu beweisen war.

Damit ist zumindest klar, daß es keine geraden vollkommenen Zahlen gibt außer den aus den Mersenne-Primzahlen gebildeten. Mit jeder neuen Mersenne-Primzahl findet man eine neue gerade vollkommenen Zahl und auch nur damit.

Bis heute ist die Frage ungeklärt, ob es ungerade vollkommenen Zahlen gibt. Man weiß jedoch, dass eine solche Zahl, wenn es sie denn gäbe, größer als 10¹⁰⁰ sein müßte und mindestens 11 verschiedenen Primteiler haben müßte.

Zum Abschluß noch ein Blick in die (mathematische) Vergangenheit. Pater Mersenne veröffentlichte im Jahr 1644 sein Buch Cogitata Physica-Mathematica, in dem er die Mersenne-Zahlen mit den Indizes n=2, 3, 5, 7, 13, 17, 19, 31, 67, 127 und 257 zu Primzahlen erklärte. Keiner weiß bis heute, wie er zu seiner Vermutung kam, denn Beweise legte er nicht vor. Allerdings hat er sich ja auch nur bei einigen Zahlenriesen getäuscht, denn M₆₇ und M₂₅₇ sind entgegen seiner Vermutung zerlegbar, während er die Primzahlen M₆₁, M₈₉ und M₁₀₇ übersah.

Um die vollkommenen Zahlen rankten schon in alten Zeiten Geschichten. Der Lehrer Karls des Großen, der Mönch Alcuin, soll geschrieben haben, daß Gott die Welt in 6 Tagen erschaffen habe und daß der Mond sich in genau 28 Tagen um die Erde drehe, zeige schon die Vollkommenheit dieser Zahlen. Die Griechen kannten sogar schon die beiden nächsten vollkommenen Zahlen 496 und 8128 (im 1.Jahrhundert n. Ch. veröffentlichte der griechische Mathematiker Nikomachos sein Werk Introductio Arithmeticae, in dem er die ersten vier vollkommenen Zahlen nennt), doch es ist mir nicht bekannt, welchen Mystizismus sie mit ihnen betrieben haben. Nikomachos vermutete übrigens, daß die n-te vollkommenen Zahl genau n Stellen habe. Tatsächlich gibt es aber gar keine vollkommene Zahl mit fünf Stellen (die fünfte vollkommene Zahl ist 33.550.336). Des weiteren stellte Nikomachos die ob des etwas dünnen Zahlenmaterials gewagte - und falsche - Behauptung auf, die vollkommenen Zahlen endeten abwechselnd auf 6 und 8. Hätte er die sechste vollkommene Zahl 8.589.869.056 gekannt, so hätte er sich seine Fehleinschätzung sparen können.

Keith Devlin berichtet in seinem Buch Sternstunden der modernen Mathematik (sehr empfehlenswert) von einem englischen Mathematiker, der 1811 über die von Euler 1772 entdeckte 19-stellige vollkommene Zahl 2³⁰(2³¹-1) schrieb: "Sie ist die größte vollkommene Zahl, die je entdeckt wurde, und sie wird es auch bleiben, denn da diese Zahlen zwar sehr merkwürdig sind, jedoch sonst keinen Nutzen haben, ist es unwahrscheinlich, daß je ein andere versuchen wird, eine noch größere vollkommenen Zahl zu finden." Wie man sich doch täuschen kann! Eulers Entdeckung war die achte von inzwischen 30 bekannten vollkommenen Zahlen. Allerdings hat sich die Rechenzeit bei den in diesem Zusammenhang auftretenden Problemen durch moderne Computer auch gewaltig verringert. So gibt Devlin an, daß für den Beweis der Zerlegbarkeit von M₈₁₉₁ (nicht etwa für die Zerlegung), 1953 ca. 100 Stunden gebraucht wurden, während derselbe Test auf einem CRAY I Computer in den achziger Jahren noch gerade 10 Sekunden benötigt wurden.

AUFGABE 1.43
a) Zeige, daß es zu jeder der ersten sechs vollkommenen Zahlen
v_i außer 6 eine Zahl n_i gibt mit v_i=1³+2³+...+n_i³. Gib diese
Zahlen n_i an.
b) Beweise: Die Summe der Kehrwerte aller Teiler einer
vollkommenen Zahlen ist 2.
c) Beweise: Jede vollkommene Zahl v gestattet die Darstellung:
v=n(n+1)

Letzte Meldung:
WAZ, Jan.97: "Nach neunmonatiger Arbeit an 18 miteinander verbundenen PC´s hat der französische Ingenieur J. Armengaud die bisher längste bekannte Primzahl entdeckt."
Es handelt sich um M_1.398.269, nach WAZ der 35. Mersenne Primzahl.

Allerletzte Meldung:
Im Jahr 1997 werden 2^2.976.221 und im Januar 1998 2^3.021.377 mit 909.526 Stellen als vorerst letzte Mitglieder ( Nummer 36 und 37) in den Klub der Mersenne-Primzahlen aufgenommen. Auffällig ist der (prozentual) geringe Abstand der beiden Riesen. Der Nachweis der Primalität der letzteren brauchte etwa eine Woche Rechenzeit auf einem 200 MHZ Pentium (ob mit oder ohne Rechenfehler, ist nicht bekannt). Interessierte können sich auf der Internetseite http://www.utm.edu/research/primes ganz aktuell auf dem Laufenden halten.

01.06.98:   2^6.972.593 mit 2.098.960 Stellen als prim entlarvt.

Download Kap1_1(15 KB)

Copyright © Michael Dorner, Dezember 2000.