Endlich oder unendlich?

Nach gängiger mathematischer Theorie gibt es unendlich viele Zahlen. Reiht man sie alle hintereinander an einem Strang auf, dann hat dieser kein Ende – man kann durch simples Addieren einer 1 immer noch eine Zahl hinzufügen. Doch wie sieht es mit den Primzahlen aus?

Schon Euklid bewies, dass Primzahlen unendlich sein müssen © historisch

Der Satz des Euklid

DieserFrage beschäftigte schon um 300 vor Christus den griechischen Mathematiker Euklid. In seinem Werk „Die Elemente“ stellt er einen mathematischen Beweis vor, mit dem sich die Frage nach der Endlichkeit der Primzahlen verblüffend einleuchtend und simpel klären lässt: den Satz des Euklid. Mit diesem Widerspruchsbeweis belegt er, dass die Primzahlen nicht endlich sein können. Euklid benötigt dabei nur wenige Primzahlen als Beispiel.

Angenommen, es gäbe nur die Primzahlen 2, 3, 5, 7 und 11 und keine weitere mehr. Euklids Formel multipliziert nun diese Primzahlen miteinander: m= 2x3x5x7x11 = 2.310. Jetzt erzeugt er die nächsthöhere Zahl, indem er eine 1 addiert. Es ergibt sich n = 2.311. Und voilà: Diese Zahl ist eine Primzahl – was beweist, dass es jenseits der 11 mehr Primzahlen gibt.

Aber das Ganze funktioniert auch dann, wenn n keine Primzahl ist. Nehmen wir 2x3x5x7x11x13 = 30.030. Addiert man nun 1, ergibt sich 30.031 – keine Primzahl. Doch zerlegt man diese Zahl in ihre Faktoren, dann stellt man fest: Die Zahl 30.031 lässt sich in zwei Primfaktoren zerlegen: 59 und 509. Beides sind Primzahlen, die höher sind als 13. Auch das beweist damit, dass unsere vermeintlich höchste Primzahl 13 nicht die höchste sein kann. Um es in Euklids Worten zu formulieren: „Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.“ Anders ausgedrückt: Es gibt unendlich viele Primzahlen.

Fahndung im Zahlenstrang

Doch die Unendlichkeit der Primzahlen hält Mathematiker und Hobby-Primzahlenjäger nicht davon ab, nach immer neuen, immer größeren Vertretern dieser „Zahlenatome“ zu suchen. Das allerdings ist selbst für heutige Hochleistungscomputer eine echte Herausforderung. Um den Rechenaufwand überhaupt zu bewältigen, nutzt man für die Identifizierung von Primzahlen heute nicht mehr Siebtechniken wie bei Eratosthenes, sondern Algorithmen, die auf Wahrscheinlichkeiten beruhen.

Dies ist die größte bisher bekannte Primzahl - eine Zahl mit mehr als 23 Millionen Stellen. © HG: iStock.com

Diese Programme nutzen bestimmte Trends aus, die Mathematiker im Laufe der Jahrhunderte bei Primzahlen entdeckt haben. Einen dieser Primzahlen-Trends beschrieb der Mönch Martin Mersenne vor rund 350 Jahren. Demnach ist die Wahrscheinlichkeit sehr hoch, dass eine Zahl, die die Gleichung 2^p -1 erfüllt, eine Primzahl ist. Der Exponent p ist dabei eine Primzahl. Nach solchen sogenannten Mersenne-Primzahlen sucht unter anderem das Citizen-Science-Projekt GIMPS. Jeder Teilnehmer bekommt dabei eine Mersenne-Zahl zugeteilt und sein Rechner prüft dann mithilfe eines speziellen Algorithmus, ob es sich wirklich um eine Primzahl handelt.

Die – bisher – größte Primzahl

Anfang 2018 gelang es einem Teilnehmer des GIMPS-Projekts, die bisher größte bekannte Primzahl zu identifizieren: 2^77232917 -1. Es handelt sich um eine Zahl mit mehr als 23 Millionen Stellen. Sein Computer hatte sechs Tage lang gerechnet, um nachzuweisen, dass dies eine Primzahl sein muss.

Allerdings: Schon jetzt ist klar, dass dieser Rekord bestenfalls vorübergehend gilt. Weil Primzahlen unendlich weitergehen, kann es nie eine endgültig allergrößte Primzahl geben. Die größte bisher bekannte Primzahl wird daher vermutlich schon bald von einer noch größeren abgelöst werden – es ist letztlich nur eine Frage der Rechenkapazität.

Nadja Podbregar
Stand: 15.06.2018