Primzahlen sind, wie Edmund Hlawka gerne sagte, „spröde Zahlen“. Ein wenig erinnern sie an chemische Elemente.
Der Begriff des chemischen Elements entstand, als nach jahrhundertelangen Versuchen der Alchemisten, aus unedlen Materialen Gold herzustellen, die Chemie ihren Siegeszug als Wissenschaft antrat. Der erste große Gegner der Alchemie war der irische Naturforscher Robert Boyle. 1661 veröffentlichte er ein Buch mit dem Titel „The Sceptical Chymist“, in dem er mit den Scharlatanen seiner Zeit abrechnete und sich über die Versuche der zeitgenössischen Goldmacher lustig machte. Nach der Durchführung vieler Versuche erkannte Boyle, woraus sich der „Stoff der Schöpfung“ – ein schönes Wort des Physikers Heinz Haber – zusammensetzt. Boyle behauptete, dass die Natur einige elementare Stoffe geschaffen habe, die fundamental existieren und die man nicht künstlich erzeugen könne.
Diese Urstoffe nannte er Elemente. Seiner Meinung nach war jeder Versuch zum Scheitern verurteilt, aus Blei oder Quecksilber Gold machen zu können. Gold sei ein Element – und damit chemisch unzerstörbar und unherstellbar.
Andere Stoffe, wie zum Beispiel Wasser oder Zinnober, sind keine Elemente, sondern chemische Verbindungen. Setzt man Wasser einer elektrischen Spannung aus, zerfällt es in Wasserstoff und Sauerstoff. Erhitzt man Zinnober mit einer Flamme, zerfällt es in Quecksilber und Schwefel.
Was für die Stoffe in der Natur gilt, stimmt auch für die Zahlen in der Mathematik. Auch sie setzen sich aus „Urbausteinen“ zusammen. Aber in der Mathematik muss man unterscheiden, ob man die Zahlen mit dem sehr einfachen Rechengesetz der Addition oder dem etwas komplizierteren Rechengesetz der Multiplikation erzeugt.
Die Entstehung der Zahlen aus der Addition ist wirklich simpel. Man geht von der ersten Zahl 1 aus. Wenn man zu ihr andauernd eins addiert, erhält man 2, 3, 4, … – alle Zahlen. Daher gibt es nur ein „Element“, aus dem sich alle Zahlen zusammensetzen: die Eins.
Die Entstehung der Zahlen aus der Multiplikation ist ein wenig verworrener, dafür auch interessanter: Wieder gehen wir von der Zahl 1 als erster Zahl aus. Aber man kommt mit der Eins, wenn man multipliziert, nicht über sie hinaus: Wie oft man auch 1 mit sich selbst multipliziert, immer wird nur 1 das Ergebnis sein.
Das erste eigentliche „Element“ der Zahlen – aus der Sicht der Multiplikation – ist die Zahl 2. Aus ihr entstehen der Reihe nach die Zahlen 2 × 2 = 22 = 4, 2 × 2 × 2 = 23 = 8, 2 × 2 × 2 × 2 = 24 = 16 und so weiter. Aber alle Zahlen erhält man auf diese Weise noch nicht. Die kleinste Zahl, die in dieser Liste fehlt, ist 3. Daher hat man neben 2 auch noch 3 als „Element“ im Zahlenreich aufzunehmen. Solche „Elemente“ wie 2 oder 3 nennt man in der Mathematik Primzahlen – ein Wort gebildet aus dem lateinischen „primus“, der Erste. Denn man beginnt mit den Primzahlen, alle Zahlen aus Multiplikationen zu bilden.
Mit den Primzahlen 2 und 3 kommt man beim Multiplizieren zu den Zahlen 2 × 2 = 4, 2 × 3 = 6, 2 × 2 × 2 = 8, 3 × 3 = 9, 2 × 2 × 3 = 12 und so weiter: Wie man sieht, werden noch immer nicht alle Zahlen dargestellt. Die nächsten Zahlen, die in der Liste fehlen, sind 5 und 7. Auch sie sind Primzahlen.
Es war der brillante Einfall der griechischen Gelehrten Euklid von Alexandria und Eratosthenes von Kyrene, beide eine Generation nach Alexander dem Großen in der Bibliothek von Alexandria tätig, diesen Gedanken auszubauen:
Euklid fand heraus, dass mit keiner endlichen Liste von Primzahlen alle Zahlen als Produkte der Primzahlen aus der Liste dargestellt werden können. Welche Produkte man aus den Primzahlen der endlichen Liste auch immer bildet, nie werden alle Zahlen von diesen Produkten erschlossen. Euklid begründet dies so: Er berechnet das Produkt aller Primzahlen der Liste und addiert zu diesem Resultat die Zahl 1. Auf diese Weise hat er eine Zahl gefunden, die durch keine Primzahl der Liste teilbar sein kann. Diese Zahl ist daher kein Produkt von Primzahlen der vorgelegten Liste.
Verdeutlichen wir Euklids Überlegung anhand eines konkreten Beispiels: Angenommen, jemand behauptet, die Zahlen 2, 3, 5, 7, 11 und 13 bildeten die Gesamtheit aller Primzahlen, mehr gäbe es nicht. Dann müsste, so argumentiert Euklid, die Zahl 2 × 3 × 5 × 7 × 11 × 13 + 1, die sich als 30 031 errechnet, als Produkt von Primzahlen dieser Liste schreiben lassen. Doch das ist sicher falsch: Durch keine der Primzahlen der Liste ist 30 031 teilbar, immer bleibt bei der Division der Rest 1. Und weil 30 031 nicht als Produkt der Primzahlen aus der Liste 2, 3, 5, 7, 11, 13 geschrieben werden kann, muss es mehr Primzahlen als die in der Liste genannten geben. Nebenbei bemerkt: Tatsächlich kommen die Primzahlen 59 und 509 in der genannten Liste nicht vor, und es ist 30 031 = 59 × 509.
Eratosthenes gelang es, systematisch eine Liste der Primzahlen zwischen 2 und 100 zu erstellen. Sie lauten
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
und scheinen gesetzlos aufeinanderzufolgen. So als ob es keine Regelmäßigkeiten gibt. Eratosthenes wusste auch, wie man seine Systematik ausbauen konnte und zum Beispiel alle Primzahlen zwischen 1 und 1000 gewinnt. Aber das Argument des Euklid besagt, dass keine Liste alle Primzahlen aufzählen kann. Keine endliche Liste von Primzahlen ist vollständig.
Das eigenartig sporadische Auftreten der Primzahlen setzt sich fort: So klafft zwischen den aufeinanderfolgenden Primzahlen 19 609 und 19 661 eine ziemlich große Lücke. Die Primzahlen 19 697 und 19 699 hingegen unterscheiden sich nur um die Differenz zwei. Ein einfaches Gesetz, das die Folge der Primzahlen beschreibt, scheint nicht zu existieren.
Insbesondere wissen wir noch immer nicht, ob 4 294 967 297 eine Primzahl ist oder nicht …
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.)