Beweis, dass es unendlich viele Primzahlen gibt

Dieser Beweis wird zeigen, dass es unendlich viele Primzahlen gibt. Der Beweis wird dabei durch Widerspruch geführt werden. Wir beweisen also, das es falsch wäre, anzunehmen, es gäbe eine endliche Menge an Primzahlen.

Primzahlen: eine Einführung

Wir wir wissen, sind Primzahlen eine Teilmenge der ganzen Zahlen. Eine Primzahl ist definiert als eine Zahl, die nur durch 1 und sich selbst teilbar ist. Daher ist 5 eine Primzahl, weil sie nur durch sich selbst und 1 exakt teilbar ist. Gleichermaßen ist 9 keine Primzahl, da sie durch 1, 3 und sich selbst teilbar ist. Es gibt viele Sätz, die man auf Primzahlen anwenden kann, der Wichtigste ist wahrscheinlich der Fundamentalsatz der Arithmetik, der besagt, dass jede Zahl, die größer als 1 ist, als Produkt von Primzahlen dargestellt werden kann. Nehmen wir dazu ein Beispiel:

108 = 54 · 2 = 27 · 2 · 2 = 9 · 3 · 2 · 2 = 3 · 3 · 3 · 2 · 2

Man spricht hierbei auch von Primfaktorzerlegung. Dieses Produkt ist eindeutig; es gibt kein anderes Produkt aus Primzahlen, mit dem man die Zahl 108 darstellen könnte. Es gibt zwei weitere Vermutungen über Primzahlen.

• Die erste ist die Goldbachsche Vermutung, die besagt, dass jede Zahl die größer als 2 ist als Summe zweier Primzahlen geschrieben werden kann. Man kann beispielsweise die Zahl 18 als 11+7 und die Zahl 15 als 13+2 schreiben.
• Die zweite Vermutung ist, dass eine unendliche Anzahl an Zwillingsprimzahlen existiert, also Primzahlen, deren Differenz 2 ist, wie beispielsweise 5 und 7 oder 11 und 13.

Beide Vermutungen über Primzahlen konnten weder vollständig mathematisch bewiesen noch widerlegt werden.

Beweis

Jetzt geht es an den Beweis. Wir werden den Beweis durch Widerspruch führen, wir werden also beweisen, dass ein Widerspruch entstehen würde, wenn das zu Beweisende falsch wäre.

Zuerst müssen wir die Aussage formulieren, die wir beweisen wollen:

P = Es gibt eine unendliche Anzahl an Primzahlen

Dann formulieren wir das Gegenteil dieser Aussage:

N = Es gibt eine endliche Anzahl an Primzahlen

Nur eine der beiden Aussagen kann richtig sein. Teil der Beweisführung durch Widerspruch ist, zunächst anzunehmen, dass die Aussage N richtig ist. Nehmen wir also an, N sei richtig und P sei falsch.

Wenn N richtig ist, gibt es endliche viele Primzahlen. Das heißt auch, dass es eine höchste Primzahl geben muss. Dieser Zahl geben wir den Buchstaben h. Die Reihe der Primzahlen ist:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …

Nun definieren wir eine neue Zahl, der wir den Buchstaben n geben:

n = 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · … · h + 1

Die Zahl n ist das Produkt aller Primzahlen, plus Eins. Das Dazurechnen von Eins hat eine entscheidende Auswirkung: unsere Zahl n ist nicht mehr exakt durch irgendeine der Primzahlen aus unserer endlichen Reihe teilbar. Daraus entstehen zwei mögliche Erklärungen:

1. n ist selbst eine Primzahl
2. n ist teilbar durch eine Primzahl die größer als h ist

Wenn die erste Erklärung stimmt, so hätten wir bewiesen, dass es eine größere Primzahl als h gäbe, da n zweifelsohne größer als h ist. Die zweite Erklärung geht einher mit dem Fundamentalsatz der Arithmetik, der bekanntermaßen besagt, dass sich jede Zahl als Produkt von Primzahlen ausdrücken lässt. Da n nicht durch eine der bekannten Primzahlen teilbar ist, muss es durch eine Primzahl die größer als h ist, teilbar sein.

In beiden Fällen haben wir allerdings bewiesen, dass h nicht die größte Primzahl ist. Die Aussage N kann also nicht korrekt sein. Daher muss die Aussage P richtig sein und es eine unendliche Anzahl an Primzahlen geben.

Dieser Beweis geht auf den griechischen Mathematiker Euklid zurück, der um 300 v. Chr. in Alexandria lebte. Er veröffentlichte ihn in seinem Werk Die Elemente, welches noch 2000 Jahre nach dessen Veröffentlichung als Standardwerk benutzt wurde und neben der Bibel als das meistverbreitete Werk der Weltliteratur gilt.