Die Zahl, die aus der Kalte kam: Wenn Mathematik zum Abenteuer wird

Die Sucht nach Primzahlen

Im Frankreich zur Zeit Richelieus, zu einer Zeit, als die Adeligen und reichen Bürger genügend Zeit für scheinbar nutzlose Beschäftigungen hatten, dilettierten im besten Sinne des Wortes einige von ihnen über Primzahlen. Zu ihnen zählten der am Cours de Monnaies tätige Finanzbeamte Bernard Frénicle de Bessy, der gebildete Paulanermönch Marin Mersenne und der Rechtsanwalt und parlamentarische Rat Pierre de Fermat. Vor allem bemühten sie sich, Formeln zu finden, die in großer Menge, ja vielleicht überhaupt nur Primzahlen lieferten.

Eines der trügerischen Rezepte für Primzahlen, an dem sie sich abarbeiteten, lautet: „Man nehme eine Zahl, addiere dazu ihr Quadrat und die Zahl 41. Dann erhält man eine Primzahl.“ Anfangs sehen die Ergebnisse vielversprechend aus: Nimmt man 1, lautet dessen Quadrat 12 = 1, und die beiden Zahlen zu 41 addiert ergeben die Primzahl 43, Nimmt man 2, lautet dessen Quadrat 22 = 4. Die beiden Zahlen zu 41 addiert ergeben die Primzahl 47. Bei der 3 lautet das Ergebnis 53, ebenfalls eine Primzahl. Bei der 4 und der 5 kommt man auf die Primzahlen 61 und 71. Und damit ist es noch lange nicht zu Ende. Nimmt man zum Beispiel 10 und addiert dazu dessen Quadrat 102 = 100 sowie die Zahl 41, bekommt man die Primzahl 151. Oder nimmt man 36 und addiert dazu dessen Quadrat 362 = 1296 sowie die Zahl 41, ist das Resultat die Primzahl 1373. Für alle Zahlen von 1 bis 39 liefert das Rezept Primzahlen. Aber bei 40 ist Schluss. Denn addiert man zu 40 dessen Quadrat 402 = 40 × 40, berechnet man die Zahl 40 × 41. Und wenn man zu dieser noch 41 addiert, hat man 41 × 41 = 412 berechnet. Und das kann keine Primzahl sein. (Es ist schön, dass man für diese Feststellung gar nicht zu rechnen braucht. Natürlich kann man ebenso gut argumentieren, dass 40 zu seinem Quadrat 402 = 1600 addiert die Zahl 1640 ergibt und dies um 41 vermehrt auf 1681 führt. Und man kann leicht bestätigen, dass 1681 = 412 = 41 × 41 keine Primzahl ist. Aber offenkundig ist das die Rechnung vermeidende Argument weitaus eleganter.)

Marin Mersenne fand ein anderes Rezept. Er zog von Potenzen von 2, also von den Zahlen

22 = 4, 23 = 8, 24 = 16, 25 = 32, 26 = 64, 27 = 128,

28 = 256, 29 = 512, …

immer 1 ab und stellte fest: Nur wenn die Hochzahl eine Primzahl ist, ergibt die Differenz der Zahl 1 von der Zweierpotenz eine Primzahl. In der Tat sind

22 − 1 = 3, 23 − 1 = 7, 25 − 1 = 31, 27 − 1 = 127

lauter Primzahlen. Die Differenz der Zahl 1 von einer Zweierpotenz mit einer Hochzahl, die zusammengesetzt ist, kann keinesfalls Primzahl sein, wie schon die Rechnungen

24 − 1 = 15 = (22 − 1) × (1 + 22) = 3 × 5,

26 − 1 = 63 = (23 − 1) × (1 + 23) = 7 × 9,

28 − 1 = 255 = (24 − 1) × (1 + 24) = 15 × 17,

29 − 1 = 511 = (23 − 1) × (1 + 23 + 26) = 7 × 73

belegen.12 Allerdings erkannte Mersenne, dass sein Rezept nicht immer, sogar nur selten wirkt: Selbst wenn die Hochzahl von 2 eine Primzahl ist, muss die Differenz der Zahl 1 von dieser Zweierpotenz keine Primzahl sein. Zwar stimmt sein Rezept für die Hochzahlen 2, 3, 5 und 7, aber mit der Primzahl 11 als Hochzahl ist auch hier wieder Schluss. Denn 211 − 1 = 2047 ist das Produkt von 23 und 89.

Ganz Schluss aber ist nicht. Mersenne überprüfte, ob sein Rezept vielleicht noch bei anderen Primzahlen als Hochzahlen wirkt. Tatsächlich stellt er fest, dass

213 − 1 = 8191, 217 − 1 = 131 071 und 219 − 1 = 524 287

Primzahlen sind. Er behauptete, dies träfe auch für die Hochzahlen 31, 67, 127 und 257 zu, sonst aber für keine dazwischen. Ein wenig irrte er sich: Nicht 267 − 1, sondern 261 − 1 ist eine Primzahl, auch 289 − 1 und 2107 − 1 sind Primzahlen, dafür ist 2257 − 1 keine Primzahl. Die Hochzahlen unter 500, bei denen die Differenz der Zahl 1 von der entsprechenden Zweierpotenz eine Primzahl liefert, lauten:

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

Die größte dieser Differenzen, die aus 39 Stellen bestehende Zahl

2127 − 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727,

wurde erst 1876 vom französischen Gymnasiallehrer Edouard Lucas als Primzahl identifiziert. Es ist die größte Primzahl, die jemals mit Hand berechnet wurde.

Erst ab 1950 hat man mit elektronischen Rechnern nach dem Rezept von Mersenne noch größere Primzahlen ermittelt und fand bei über dreißig weiteren Differenzen der Zahl 1 von Zweierpotenzen riesige Primzahlen, darunter welche mit mehr als einem Dutzend Millionen Stellen.

Pierre de Fermat wollte seinen Brieffreund Mersenne in der Suche nach großen Primzahlen übertrumpfen. Er brütete ein anderes Rezept aus, das folgendermaßen lautet: Offenkundig ist 3, die Summe von 1 und 2, eine Primzahl, genauer: die erste ungerade Primzahl. Addiert man zu ihr 2, erhält man wieder eine Primzahl, nämlich 3 + 2 = 5. Nun multiplizierte Fermat diese beiden Primzahlen und addierte wieder 2. Er berechnete also 3 × 5 + 2 und erhielt so 17. Auch dies ist eine Primzahl. Als Nächstes multiplizierte er seine drei so gefundenen Zahlen – ihm zu Ehren werden sie „Fermatsche Zahlen“ genannt – und addierte wieder 2. Jetzt bekam er bereits eine recht große Zahl, nämlich

3 × 5 × 17 + 2 = 257,

und auch sie ist Primzahl. Fermat war von seinem Rezept fasziniert. Er addierte zum Produkt der ersten vier Fermatschen Zahlen 3, 5, 17, 257 die Zahl 2, erhielt die fünfte Fermatsche Zahl

3 × 5 × 17 × 257 + 2 = 65 537

und mühte sich viele Stunden ab, um zu kontrollieren, ob diese Zahl eine Primzahl ist. Sie ist es. Jetzt begann er, an die universelle Gültigkeit seines Rezepts zu glauben. Begeistert schrieb er 1640 in einem Brief an Frenicle de Bessy: „Aber hier ist das, was ich am meisten bewundere: Es ist, dass ich nahezu überzeugt bin, dass die Zahlen13

1 + 2 = 3, 1 × 3 + 2 = 5, 1 × 3 × 5 + 2 = 17,

1 × 3 × 5 × 17 + 2 = 257,

1 × 3 × 5 × 17 × 257 + 2 = 65 537,

1 × 3 × 5 × 17 × 257 × 65 537 + 2 = 4 294 967 297,

und die folgende aus zwanzig Ziffern bestehende Zahl

1 × 3 × 5 × 17 × 257 × 65 537 × 4 294 967 297 + 2 =

18 446 744 073 709 551 617; etc.

Primzahlen sind. Ich habe dafür keinen exakten Beweis, habe aber eine große Anzahl von Teilern durch unfehlbare Beweise ausgeschlossen, und meine Überlegungen beruhen auf einer solch klaren Einsicht, dass ich kaum fehlgehen kann.“

Hier ist sie, die Zahl 4 294 967 297, von der wir zu Beginn des Kapitels ausgegangen sind. Sie ist die sechste Fermatsche Zahl. Selbst heute ist es, wenn einem nur Bleistift und Papier zur Verfügung stehen, allzu zeitraubend zu überprüfen, ob diese Zahl eine Primzahl ist.

Zwei große Zahlen miteinander zu multiplizieren ist leicht. Herauszufinden, aus welchen Teilern eine große Zahl besteht, ist hingegen außerordentlich mühsam. 1732, knapp hundert Jahre nachdem Fermat diesen Brief verfasst hatte, entdeckte der emsige Schweizer Mathematiker Leonhard Euler, dass sich Fermat in seiner Überzeugung irrte: Die sechste Fermatsche Zahl 4 294 967 297 ist durch 641 teilbar.14

Dieser kleine Lapsus schmälert keineswegs Fermats überragendes Talent im Aufspüren von geheimen Gesetzen hinter den Zahlen. Übrigens hat man die weiteren, auf 4 294 967 297 und 18 446 744 073 709 551 617 folgenden Fermatschen Zahlen untersucht und bislang keine weitere Primzahl unter ihnen gefunden. Und da die Fermatschen Zahlen explosionsartig wachsen, sind solche Untersuchungen unerhört subtil.

Lange Zeit war es pures Vergnügen weltfremd versponnener Zahlenliebhaber, sich mit Primzahlen zu beschäftigen. Denn es schien nichts zu geben, wozu Primzahlen gut sein könnten. Sie sind einfach im Zahlenreich vorhanden wie Goldkörner im Schlamm Alaskas, aber das Gold der Primzahlen schien wertlos zu sein.

In den Siebzigerjahren des vorigen Jahrhunderts stellte sich plötzlich heraus, dass dem nicht so ist. Primzahlen, vor allem große Primzahlen, sind unerhört viel wert, mehr als Gold und Edelstein. Denn sie verhelfen zu ungeahnter Macht. Um das verstehen zu können, müssen wir uns in die düstere Welt der Spione begeben.