Eine berechtigte Vermutung
Am letzten Abend haben wir gesehen: Die Primzahlen werden dünner. 25 im ersten Hunderter, 21 im zweiten, 16 im dritten. Wer das fortschreibt, kommt auf eine naheliegende Vermutung — irgendwann müsste Schluss sein. Irgendwo da draußen liegt die größte Primzahl, und danach kommt nichts mehr.
Die Vermutung ist falsch. Und der Beweis dafür ist rund 2 300 Jahre alt, steht in Euklids Elementen und passt auf eine halbe Seite. Er gehört zum Schönsten, was die Mathematik zu bieten hat.
Euklids Beweis
Wir nehmen das Gegenteil an und führen es zum Widerspruch.
Annahme: Es gibt nur endlich viele Primzahlen. Dann können wir sie alle aufschreiben:
p₁, p₂, p₃, …, pₙ
Das ist die vollständige Liste. Keine fehlt.
Jetzt bauen wir eine neue Zahl. Wir multiplizieren alle miteinander und addieren 1:
N = p₁ · p₂ · p₃ · … · pₙ + 1
Diese Zahl N ist größer als jede Primzahl der Liste. Zwei Fälle sind möglich:
Fall 1: N ist selbst prim. Dann haben wir eine Primzahl gefunden, die nicht auf der Liste steht — denn N ist ja größer als alle. Die Liste war also nicht vollständig. Widerspruch.
Fall 2: N ist zusammengesetzt. Dann hat N einen Primteiler q. Dieses q muss auf unserer Liste stehen, sie war ja vollständig. Also teilt q das Produkt p₁ · p₂ · … · pₙ. Und q teilt nach Annahme auch N. Wenn aber q zwei Zahlen teilt, teilt q auch ihre Differenz:
N − (p₁ · p₂ · … · pₙ) = 1
Also müsste q die Zahl 1 teilen. Das kann keine Primzahl. Widerspruch.
Beide Fälle führen zum Widerspruch. Die Annahme war falsch:
Es gibt unendlich viele Primzahlen.
Ein verbreitetes Missverständnis
Man hört oft, Euklids Beweis zeige, dass p₁ · p₂ · … · pₙ + 1 immer eine neue Primzahl sei. Das stimmt nicht, und es ist lehrreich nachzusehen:
| Rechnung | Ergebnis | prim? |
|---|---|---|
| 2 + 1 | 3 | ja |
| 2 · 3 + 1 | 7 | ja |
| 2 · 3 · 5 + 1 | 31 | ja |
| 2 · 3 · 5 · 7 + 1 | 211 | ja |
| 2 · 3 · 5 · 7 · 11 + 1 | 2 311 | ja |
| 2 · 3 · 5 · 7 · 11 · 13 + 1 | 30 031 | nein: 59 · 509 |
Bei der sechsten Zeile bricht es. 30 031 ist zusammengesetzt — aber seine Primteiler 59 und 509 stehen eben nicht auf unserer Liste. Genau das behauptet der Beweis, und nur das. Er liefert keine neue Primzahl, er beweist nur, dass es eine geben muss.
Beliebig große Lücken
Unendlich viele Primzahlen — heißt das, sie liegen überall gleichmäßig verteilt? Nein. Im Gegenteil lässt sich zeigen, dass es beliebig lange primzahlfreie Strecken gibt. Auch dieser Beweis ist kurz.
Nehmen Sie eine Zahl, sagen wir 5, und bilden Sie die Fakultät 5! = 1 · 2 · 3 · 4 · 5 = 120. Dann betrachten Sie:
120 + 2 = 122 durch 2 teilbar
120 + 3 = 123 durch 3 teilbar
120 + 4 = 124 durch 4 teilbar
120 + 5 = 125 durch 5 teilbar
Vier zusammengesetzte Zahlen hintereinander. Der Grund ist einfach: 120 enthält den Faktor 2, also ist 120 + 2 durch 2 teilbar; 120 enthält den Faktor 3, also ist 120 + 3 durch 3 teilbar, und so fort.
Mit 100! statt 5! bekommt man auf dieselbe Weise 99 zusammengesetzte Zahlen hintereinander. Mit 1 000 000! eine Million. Es gibt also Wüsten beliebiger Länge — und trotzdem geht es dahinter immer weiter.
Das ist die eigenartige Spannung, um die sich die ganze Primzahlforschung dreht: unendlich viele, aber mit beliebig großen Löchern dazwischen.
Die größte bekannte Primzahl
Unendlich viele heißt nicht, dass wir sie kennen. Die größte bekannte Primzahl wird regelmäßig von einem verteilten Rechenprojekt gefunden und hat inzwischen mehr als 40 Millionen Stellen — ausgedruckt wären das mehrere tausend Seiten für eine einzige Zahl.
Es sind fast immer sogenannte Mersenne-Zahlen der Form 2ᵖ − 1, weil es für diese Form einen besonders schnellen Test gibt. Doch Vorsicht: Nicht jede Zahl dieser Form ist prim.
2² − 1 = 3 prim
2³ − 1 = 7 prim
2⁵ − 1 = 31 prim
2⁷ − 1 = 127 prim
2¹¹ − 1 = 2047 = 23 · 89 nicht prim
Auch hier wieder: ein schönes Muster, das genau dann bricht, wenn man anfängt, sich darauf zu verlassen.
Am Rechner
Unter Werkzeuge · Lücken & Zwillinge sehen Sie die Rekordlücken — die jeweils größte primzahlfreie Strecke bis zu einer Schranke. Achten Sie darauf, wie unregelmäßig die Rekorde fallen.
Übungen
Wie viele Primzahlen gibt es?
1. Rechnen Sie 2 · 3 · 5 · 7 + 1 aus und prüfen Sie, ob das Ergebnis prim ist.
2. Rechnen Sie 2 · 3 · 5 · 7 · 11 · 13 + 1 aus. Das Ergebnis ist nicht prim — finden Sie die beiden Faktoren. Was sagt das über Euklids Beweis aus?
3. Finden Sie sieben aufeinanderfolgende Zahlen unter 100, von denen keine einzige prim ist.
4. Konstruieren Sie mit dem Fakultäts-Trick sechs aufeinanderfolgende zusammengesetzte Zahlen. Mit welcher Fakultät fangen Sie an?
5. Wie groß ist die Lücke zwischen 113 und der nächsten Primzahl? Suchen Sie die nächste Primzahl von Hand.
6. Ist 2¹³ − 1 = 8 191 eine Primzahl? Wie weit müssen Sie testen?
Zum Nachdenken. Euklids Beweis zeigt, dass es unendlich viele Primzahlen gibt. Zugleich gibt es beliebig lange Strecken ohne eine einzige. Ist das ein Widerspruch? Begründen Sie Ihre Antwort in drei Sätzen.
Lösungen anzeigen— erst selbst rechnen lohnt sich
1. 2 · 3 · 5 · 7 = 210, also 210 + 1 = 211.
211 ist prim. Prüfung bis √211 ≈ 14,5, also gegen 2, 3, 5, 7, 11, 13 — keiner teilt (siehe Abend 2, Aufgabe 3).
2. 2 · 3 · 5 · 7 · 11 · 13 = 30 030, also 30 031 = 59 · 509.
Beide Faktoren sind prim. Entscheidend ist: 59 und 509 stehen nicht in der Liste 2, 3, 5, 7, 11, 13. Genau das besagt Euklids Beweis — nicht, dass die konstruierte Zahl prim ist, sondern dass ihre Primteiler neu sein müssen. Die Annahme „unsere Liste ist vollständig" wird dadurch widerlegt.
3. 90, 91, 92, 93, 94, 95, 96 — sieben Stück.
| Zahl | Zerlegung |
|---|---|
| 90 | 2 · 3² · 5 |
| 91 | 7 · 13 |
| 92 | 2² · 23 |
| 93 | 3 · 31 |
| 94 | 2 · 47 |
| 95 | 5 · 19 |
| 96 | 2⁵ · 3 |
Davor liegt 89, dahinter 97 — beide prim. Die 91 ist dabei die unauffälligste; wer schnell hinsieht, hält sie für prim.
4. Man braucht 7! = 5 040. Dann sind
5042, 5043, 5044, 5045, 5046, 5047
sechs aufeinanderfolgende zusammengesetzte Zahlen, denn 5 040 + k ist für k = 2 … 7 jeweils durch k teilbar.
Allgemein liefert n! die Strecke n! + 2 bis n! + n, also n − 1 Zahlen. Für sechs Zahlen braucht man n = 7.
Hinweis: Das ist nicht die kleinste solche Strecke — die liegt viel früher (bei 90). Der Fakultäts-Trick ist keine effiziente Methode, sondern ein Beweis, dass es solche Strecken in jeder Länge gibt.
5. Nach 113 kommt 127. Die Lücke beträgt 14.
Dazwischen: 114 (gerade), 115 (durch 5), 116, 117 (durch 3), 118, 119 = 7 · 17, 120, 121 = 11², 122, 123 (durch 3), 124, 125 = 5³, 126.
Das ist die erste Lücke der Größe 14 und ein Rekord — bis dahin war die größte Lücke 8 (zwischen 89 und 97).
6. 8 191 ist prim.
Zu testen bis √8191 ≈ 90,5, also gegen die 24 Primzahlen bis 89. Keine teilt.
8 191 = 2¹³ − 1 ist damit die fünfte Mersenne-Primzahl, nach 3, 7, 31 und 127.
Zum Nachdenken. Es ist kein Widerspruch. Eine mögliche Antwort:
„Unendlich viele" sagt etwas darüber, dass die Folge nie abbricht — zu jeder Primzahl gibt es eine größere. „Beliebig große Lücken" sagt etwas darüber, wie weit der Abstand zwischen zwei benachbarten werden kann. Beides lässt sich gleichzeitig erfüllen: Die Folge geht immer weiter, nur die Schritte dazwischen werden gelegentlich sehr groß.
Ein Bild dazu: Auch die Quadratzahlen 1, 4, 9, 16, 25 … hören nie auf, und ihre Abstände wachsen trotzdem unbegrenzt.