Gibt es unendlich viele Primzahlen?

Ja. Euklid bewies das um 300 v. Chr. Egal wie viele Primzahlen du in einer Liste sammelst, das Argument konstruiert eine Zahl, deren Primfaktoren alle außerhalb dieser Liste liegen, also muss mindestens eine neue Primzahl existieren.

Zeigt Euklids Beweis, dass N = (p1 mal p2 mal ... mal pk) + 1 immer prim ist?

Nein, und das ist die häufigste Fehlerdarstellung des Beweises. N muss nur einen Primfaktor haben, der nicht auf der Liste steht, was N selbst sein kann oder eine kleinere Zahl. Zum Beispiel: 2 mal 3 mal 5 mal 7 mal 11 mal 13 + 1 = 30031, was NICHT prim ist: 30031 = 59 mal 509. Sowohl 59 als auch 509 sind Primzahlen, die in der Liste {2,3,5,7,11,13} fehlen, also funktioniert der Beweis einwandfrei.

Was für ein Beweis ist Euklids Argument?

Es ist ein Widerspruchsbeweis (reductio ad absurdum). Du nimmst das Gegenteil von dem an, was du beweisen möchtest, nämlich dass es nur endlich viele Primzahlen gibt, und zeigst dann, dass diese Annahme zu einem Widerspruch führt.

Hängt das mit Cantors Diagonalargument oder Goodsteins Satz zusammen?

Alle drei gehören zur selben Familie von Ergebnissen, bei denen eine einfache Konstruktion jeden Versuch einer vollständigen endlichen (oder abzählbaren) Beschreibung zunichtemacht. Euklid schlägt jede endliche Liste von Primzahlen, Cantor schlägt jede abzählbare Liste reeller Zahlen, und Goodstein erzeugt eine Folge, die die Beweiskraft der Peano-Arithmetik schlägt.

Euklids Beweis, dass es unendlich viele Primzahlen gibt

Irgendwann um 300 v. Chr. schrieb Euklid ein Argument auf, das kurz genug ist, um in einen einzigen Absatz zu passen. Es wurde seitdem nicht verbessert, weil es nicht verbessert werden kann. Die Behauptung ist, dass die Primzahlen ewig weitergehen, und der Beweis ist eine Konstruktion: gib mir irgendeine endliche Liste von Primzahlen, und ich werde dir eine Primzahl geben, die nicht darauf steht.

Zweitausend Jahre später hat das Argument noch immer die Qualität eines guten Zaubertricks. Du siehst jeden Schritt klar. Du weißt genau, wie es endet. Und es landet trotzdem.

Was eine Primzahl ist, und warum die Frage wichtig ist

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Die ersten sind 2, 3, 5, 7, 11, 13. Sie sitzen innerhalb der ganzen Zahlen wie Atome: jede andere ganze Zahl entsteht durch Multiplizieren von Primzahlen. Die Zahl 30 zum Beispiel zerfällt in 2 mal 3 mal 5, und es gibt im Wesentlichen nur eine Möglichkeit, diese Zerlegung durchzuführen.

Da Primzahlen die Bausteine aller ganzen Zahlen sind, ist es natürlich zu fragen: gehen sie aus? Gibt es eine größte Primzahl, nach der der Brunnen trocken ist? Euklids Antwort lautet nein, und der Weg, den er nimmt, ist elegant genug, um ihm in einer einzigen Sitzung zu folgen.

Das Setup: Nimm an, die Liste ist vollständig

Das Argument ist ein Widerspruchsbeweis. Du beginnst damit, dem Gegenüber alles zu geben, was es will.

Nimm an, es gibt nur endlich viele Primzahlen

Angenommen, zur Argumentation, die vollständige Sammlung aller Primzahlen ist eine endliche Liste: p1, p2, p3, bis hinauf zu pk. Keine Primzahlen existieren außerhalb dieser Liste. Das ist die Annahme, die wir zerstören werden.

Nachdem du nun jede existierende Primzahl in diese Liste gesammelt hast, baue aus ihnen eine neue Zahl.

Die Zahl konstruieren, die die Liste bricht

Bilde N, indem du alle aufgelisteten Primzahlen multiplizierst und 1 addierst

Sei N = (p1 mal p2 mal p3 mal ... mal pk) + 1. Das heißt: nimm das Produkt jeder Primzahl auf der vermeintlich vollständigen Liste und addiere dann 1.

Das ist der entscheidende Zug, und es lohnt sich, innezuhalten, um zu sehen, was er bewirkt. Das Multiplizieren aller aufgelisteten Primzahlen ergibt eine Zahl, durch die jede Primzahl auf der Liste glatt teilt. Das Addieren von 1 stört sie alle auf einmal.

Wenn du N durch p1 teilst, bekommst du einen Rest von 1, weil das Produkt (p1 mal p2 mal ... mal pk) durch p1 teilbar ist, und das Addieren von 1 verschiebt den Rest auf 1. Dieselbe Logik gilt für p2, für p3, für jede Primzahl auf der Liste. Keine von ihnen teilt N glatt.

Der Widerspruch

N hat einen Primfaktor, aber dieser Faktor kann nicht auf der Liste stehen

Jede ganze Zahl größer als 1 hat mindestens einen Primfaktor. Das ist eine Folge des Fundamentalsatzes der Arithmetik: zerlege weiter, bis du nicht mehr kannst, und du bleibst bei Primzahlen. Also hat N einen Primfaktor. Nenn ihn q.

Wir haben gerade gezeigt, dass keine Primzahl auf der Liste N teilt. Daher steht q nicht auf der Liste. Aber wir haben angenommen, die Liste enthält jede Primzahl. Das ist der Widerspruch: wir haben eine Primzahl q gefunden, die nicht auf der vermeintlich vollständigen Liste steht.

Die Annahme muss falsch sein

Da die Annahme, dass es nur endlich viele Primzahlen gibt, direkt zu einem Widerspruch führt, ist die Annahme falsch. Es gibt keine endliche Liste, die alle Primzahlen enthält. Die Primzahlen gehen ewig weiter.

Das Gegenbeispiel, das den Beweis ehrlich macht

Hier gehen viele populäre Darstellungen von Euklids Beweis in die Irre. Sie behaupten, dass N selbst immer prim ist. Das ist nicht so, und der Unterschied ist wichtig.

Nimm die Liste 13. Das Produkt ist 2 mal 3 mal 5 mal 7 mal 11 mal 13, was 30030 ergibt. Addiere 1 und du erhältst N = 30031.

Ist 30031 prim? Nein.

30031 = 59 mal 509.

Sowohl 59 als auch 509 sind prim, und keine erscheint in der Liste 13. Das ist genau das, was der Beweis vorhersagt: nicht, dass N prim ist, sondern dass Ns Primfaktoren in der Liste fehlen. In diesem Fall sind die Primfaktoren 59 und 509, zwei Primzahlen, die aus der endlichen Liste weggelassen wurden. Das Argument ist bestätigt, aber die Bestätigung kommt von den Faktoren, nicht von N selbst.

Was der Beweis wirklich sagt

Es lohnt sich, bei der Form des Arguments innezuhalten, denn es ist ungewöhnlich klar.

Du konstruierst die fehlende Primzahl nicht explizit. Du suchst nicht nach ihr. Du beweist, dass sie existieren muss, indem du zeigst, dass das Gegenteil zu einer logischen Sackgasse führt. Die Primzahl q, die sich in den Faktoren von N versteckt, kann leicht zu finden sein (wie 59 und 509, wenn du ein paar kleine Teiler von 30031 ausprobierst) oder sie kann riesig sein. Der Beweis interessiert sich nicht dafür. Seine Kraft kommt aus der Unvermeidlichkeit: welche Liste du auch übergibst, die Konstruktion findet eine Lücke.

Das verbindet sich natürlich mit anderen Beweisen, die nach demselben Geist des "nimm das Gegenteil an und schau, wie es zusammenbricht" vorgehen. Cantors Diagonalargument verwendet dieselbe Struktur in größerem Maßstab: nimm eine vollständige Liste reeller Zahlen an, und konstruiere dann eine reelle Zahl, die nachweislich nicht darauf steht. Das Echo Euklids ist unverkennbar.

Warum die Primzahlen nie ganz ausdünnen

Eine Sache, die der Beweis dir nicht sagt, ist, wie weit Primzahlen auseinander liegen können, oder wie groß die nächste Primzahl nach einer gegebenen sein könnte. Euklids Argument garantiert nur die Existenz: irgendwo jenseits jeder endlichen Sammlung lebt eine weitere Primzahl. Die Verteilung der Primzahlen über die Zahlengerade ist eine viel schwierigere Frage und bleibt heute eines der tiefsten offenen Gebiete der Mathematik.

Was der Beweis dir sagt, ist strukturell. Die Primzahlen können durch keine endlichen Mittel erschöpft werden. Du könntest ein Leben damit verbringen, Primzahlen aufzulisten, und du würdest immer in einen unendlichen Rest hineinlisten. Jede Primzahl, die du findest, war real, aber die vor dir waren genauso real, genauso zahlreich und genauso unerreichbar durch eine endliche Liste.

Für ein Gespür dafür, wie schnell Zahlen wachsen können, wenn man mit Multiplikation und Exponenten baut, ist der Artikel über Exponenten intuitiv verstehen ein natürlicher Begleiter: das Produkt p1 mal p2 mal ... mal pk wächst schneller, als du vielleicht erwartest, und dieses Wachstum ist ein Teil des Grundes, warum N so schnell so groß wird.

Das Zen davon

Euklids Beweis ist mehr als zwei Jahrtausende alt, und Mathematiker haben seitdem Hunderte von Beweisen desselben Ergebnisses gefunden. Keiner davon hat diesen obsolet gemacht. Er behält seinen Platz nicht, weil er der cleverste oder allgemeinste ist, sondern weil er der transparenteste ist.

Du siehst das gesamte Argument in einem Durchgang. Die Konstruktion ist natürlich. Der Widerspruch ist scharf. Es gibt keinen Schritt, bei dem du etwas auf Treu und Glauben akzeptieren oder darauf vertrauen musst, dass eine komplizierte Maschine das tut, was sie behauptet.

Was der Beweis dich im Kopf behalten lässt, ist eine einzige Idee: jede endliche Liste von Primzahlen ist bereits unvollständig. Nicht weil die Liste schlecht gewählt ist, sondern weil Primzahlen die Art von Ding sind, das durch keine endliche Zählung gefasst werden kann. Sie gehören dem Unendlichen auf dieselbe Weise wie die ganzen Zahlen, oder die Brüche, oder die Punkte auf einer Geraden. Der Beweis sagt dir nicht, wo die nächste Primzahl ist. Er sagt dir, dass die nächste Primzahl immer da ist.

Das reicht. Das hat immer gereicht.

Für andere Ergebnisse, die denselben Geist der Unvermeidlichkeit teilen, zeigt Goodsteins Satz eine Folge, die trotz unvorstellbarem Wachstum immer zur Null zurückkehrt, mit derselben Logik des "etwas muss passieren, weil das Gegenteil unmöglich ist". Die Familie dieser Argumente ist es wert, sie zu kennen. Jedes ist ein anderer Blickwinkel auf dieselbe zugrunde liegende Tatsache: Mathematik enthält keine Schlupflöcher. Die Struktur hält.