Ich verstehe ja, dass man sich für Mathematik begeistert. Mir geht es da nicht anders: Gerne tauche ich in Bücher oder Paper ab und versuche, logische Argumentationsketten oder Berechnungen nachzuvollziehen. Und während meines Studiums habe ich mich auch mal in Aufgaben verbissen und für meine Abschlussarbeiten zum Teil monatelang herumgerätselt, bis ich schließlich eine Lösung fand. Aber als ich von Édouard Lucas' Geschichte hörte, war ich baff. Im 19. Jahrhundert brachte er ganze 19 Jahre damit zu, nachzuweisen, dass 170 141 183 460 469 231 731 687 303 715 884 105 727 eine Primzahl ist.

Mit dieser Kolumne möchte ich nicht nur sein Durchhaltevermögen ehren (sonst wäre dieser Artikel schon an dieser Stelle zu Ende), sondern auch auf die Methode zur Erkennung von Primzahlen eingehen, die er dabei entwickelte – und die bis heute Anwendung findet. Ganz nebenbei entwarf Lucas zudem das unterhaltsame Spiel »Die Türme von Hanoi«, aber darum soll es heute nicht gehen.

Schon seit Jahrtausenden begeistern sich Menschen für Primzahlen, denn sie bilden gewissermaßen das Periodensystem der Mathematik. Es sind jene Zahlen, die nur durch eins und sich selbst teilbar sind. Jede andere ganze Zahl lässt sich eindeutig als Produkt aus mehreren Primzahlen schreiben, wie 15 = 3 ⋅ 5. Einen großen Teil ihrer Faszination macht aus, dass Primzahlen etliche Geheimnisse bergen: Sie tauchen auf dem Zahlenstrahl zwar in einer gewissen Regelmäßigkeit auf, allerdings ist ihr Erscheinen von Schwankungen geprägt, die sich bislang nicht quantifizieren lassen. Diese Unvorhersehbarkeit sorgt unter Fachleuten seit etlichen Jahren für Kopfzerbrechen.

Darüber hinaus bemühen sich Mathefans dauerhaft, neue Primzahlen zu finden. Den aktuellen Rekord (Stand: Oktober 2025) markiert 2^136,279,841 − 1, eine Zahl mit 41 024 320 Ziffern. Alleine diese Zahl auszusprechen, würde rund 240 Tage dauern.

Primzahlen mit besonderer Struktur

Wer die Rekord-Primzahlen der letzten Jahre beobachtet hat, dem ist vielleicht aufgefallen, dass sie meist eine ähnliche Struktur haben: 2^p - 1 (wobei p eine Primzahl ist). Primzahlen dieser Form werden als Mersenne-Primzahlen bezeichnet. Und auch die eingangs genannte Zahl, der Lucas fast zwei Jahrzehnte seines Lebens widmete, ist eine Mersenne-Primzahl, nämlich 2¹²⁷- 1. Das Problem: Nicht für jede Primzahl p ist 2^p - 1 eine Primzahl. 2¹¹ - 1 ergibt zum Beispiel 2047 und lässt sich als Produkt aus 23 und 89 schreiben.

In den 1860er Jahren widmete sich Lucas 2¹²⁷ - 1, mit der Frage: Handelt es sich dabei um eine Primzahl oder nicht?

Und damit sah er sich mit einer gewaltigen Herausforderung konfrontiert. Denn die Zahl ist riesig – sie besteht aus 39 Ziffern – und zur damaligen Zeit stand Lucas natürlich noch kein Computer zur Verfügung. Das heißt, er musste irgendwie von Hand sicherstellen, dass 2¹²⁷ - 1 keine Teiler hat (außer 1 und sich selbst).

Eine Möglichkeit, das zu bewerkstelligen, besteht darin, alle Primzahlen bis 2¹²⁷ - 1 durchzugehen und sich zu vergewissern, dass sie die Zahl nicht teilen. Das ist natürlich extrem aufwändig – und schlicht nicht umsetzbar, wenn man nicht ausnahmslos alle kleineren Primzahlen kennt.

Der Lucas-Lehmer-Primzahltest

Aber Lucas gab sich nicht geschlagen. Mit cleveren Tricks entwickelte er eine neuartige Methode, die mit deutlich weniger Rechenaufwand einhergeht. Dafür stützte er sich auf die Erkenntnisse seines Kollegen Évariste Galois, der 1832 während eines mysteriösen Duells starb. Aber bevor wir uns in die schöne – aber zugegebenermaßen abstrakte – Mathematik von Galois und Lucas stürzen, stelle ich Lucas' Ergebnis vor, das inzwischen als Lucas-Lehmer-Primzahltest bekannt ist. Denn der lässt sich einfach durchspielen.

Um zu prüfen, ob 2^p - 1 eine Primzahl ist, entwickelte Lucas folgenden Algorithmus:

1. Bilde eine Zahlenfolge, deren erstes Glied s₀ = 4 ist und bei der sich jedes nachfolgende s_n durch s_n-1² - 2 berechnet. Die Folge lautet also: 4, 14, 194, 37 634 und so weiter.
2. 2^p - 1 ist genau dann eine Primzahl, falls das p-2-te Folgenglied, also s_p-2, restlos durch 2^p - 1 geteilt werden kann. Das heißt: Jede Mersenne-Primzahl hat diese Eigenschaft, und umgekehrt definiert jedes s_p-2 eine Mersenne-Primzahl 2^p - 1.

Anstatt also die Mersenne-Zahl durch alle Primzahlen, die kleiner als 2¹²⁷ - 1 sind, zu dividieren, reicht es laut Lucas aus, 125 Rechenschritte durchzuführen, um s₁₂₅ zu bestimmen und dann durch 2¹²⁷ - 1 zu teilen. Klingt schon deutlich einfacher, oder?

In der Praxis gibt es nur ein klitzekleines – oder besser gesagt: sehr großes – Problem. Die Folgenglieder s_n wachsen extrem schnell an. Und zwar so schnell, dass es nicht besonders sinnvoll ist, mit ihnen zu rechnen. Deshalb greifen Fachleute auf einen Trick zurück und dividieren die Folgenglieder s_n durch die Mersenne-Zahl und rechnen mit dem Rest weiter, falls die Division keine ganze Zahl ergibt. Dadurch verändert sich der zweite Teil des Algorithmus nicht – die Bedingung an Mersenne-Primzahlen ist immer noch dieselbe: Sie müssen s_p-2 teilen; nur dass s_p-2 durch diesen Trick deutlich kleiner ausfällt.

Um den Primzahltest besser nachzuvollziehen, können wir ihn an einem einfachen Beispiel durchrechnen: für die Mersenne-Zahl 2⁵ - 1, also 31. Für den von Lucas entwickelten Algorithmus müssen wir also s₃ berechnen, was 37 634 ergibt. Und wenn man diese Zahl durch 31 teilt, erhält man glatt das Ergebnis 1214. Das heißt, s₃ ist durch 2⁵ - 1 teilbar, und damit ist Letzteres eine Primzahl.

In 19 Jahren mühsamer Arbeit entwickelte Lucas diesen Primzahltest und wandte ihn auf 2¹²⁷ - 1 an. Somit konnte er zeigen, dass es sich dabei tatsächlich um eine Primzahl handelt. Bis heute ist sie die größte Primzahl, die ohne Unterstützung eines Computers gefunden wurde.

Aber Lucas hat nicht lückenlos bewiesen, dass sein Verfahren zuverlässig Mersenne-Primzahlen enttarnt. Dies gelang erst dem Mathematiker Derrick Henry Lehmer im Jahr 1930, weshalb die Methode als Lucas-Lehmer-Primzahltest bekannt ist.

Endliche Zahlenkörper

Aber warum funktioniert diese Strategie überhaupt? Ich habe bereits angedeutet, dass die Gründe dafür nicht ganz trivial sind. Tatsächlich ist der Beweis ziemlich technisch – und deshalb möchte ich Ihnen den ersparen; bei Interesse können Sie ihn auf Wikipedia nachlesen. Aber ich möchte zumindest die Idee hinter der Methode grob skizzieren.

Der Lucas-Lehmer-Primzahltest geht auf die Forschungen von Galois zurück, der Anfang des 19. Jahrhunderts Symmetrien in verschiedenen mathematischen Objekten untersucht hatte. Anders als seine Vorgänger beschränkte er sich dabei aber nicht auf geometrische Figuren, sondern betrachtete auch die Symmetrien von Gleichungen oder von Zahlenkörpern. Letzteres beschreibt eine Menge von Zahlen, in denen alle vier Grundrechenarten (also Addition, Subtraktion, Multiplikation und Division) anwendbar sind, ohne dass man die Menge verlässt. Sprich: Wenn ich zwei Zahlen aus dem Körper addiere oder dividiere, erhalte ich eine Zahl, die ebenfalls Teil des Körpers ist. Ein Beispiel für einen Zahlenkörper sind die rationalen Zahlen (die ganze Zahlen und Brüche enthalten) oder die reellen Zahlen.

Wie sich aber herausstellt, gibt es auch kleinere Zahlenkörper, die nur endlich viele ganze Zahlen von 0 bis p - 1enthalten. Damit die Eigenschaften eines Körpers erhalten bleiben, muss man die Zahlen periodisch fortsetzen; nach p - 1 folgt dann also wieder die Null: (0, 1, 2, 3, …, p - 1, 0, 1, 2, …). Solche Zahlenkörper mögen seltsam erscheinen, aber tatsächlich begegnen sie jedem von uns in unserem Alltag, sobald wir auf eine analoge Uhr schauen. Bei Ziffernblättern ist es für uns ganz selbstverständlich, dass auf die 12 wieder die 1 folgt.

Wie sich herausstellt, sind solche endlichen Zahlensysteme genau dann ein Zahlenkörper, wenn p eine Primzahl ist. Und Galois fand heraus, dass diese endlichen Zahlenkörper besondere symmetrische Eigenschaften besitzen.

Genau das nutzte Lucas bei der Entwicklung seines Primzahltests aus: Falls 2¹²⁷ - 1 eine Primzahl ist, dann müsste der entsprechende Zahlenkörper 0, 1, 2, … 2¹²⁷ - 2 bestimmte symmetrische Eigenschaften besitzen. Und um das endliche Zahlensystem zu erzeugen, muss man alle Werte, die größer als 2¹²⁷ - 1 sind, durch 2¹²⁷ - 1 teilen und den Rest berechnen. Das ist der letzte Schritt im Algorithmus von Lucas.

Ich hoffe, Sie verzeihen mir, dass ich die Details von Lucas' Argumentation weggelassen und nur die grobe Idee skizziert habe. Oftmals finde ich aber die Gedanken und Visionen hinter den mathematischen Erkenntnissen spannender als die technischen Details. Deswegen bin ich wohl Wissenschaftsjournalistin geworden. Umso wichtiger ist es aber, dass es Menschen gibt wie Édouard Lucas, die da anders ticken und nicht davor zurückschrecken, notfalls 19 Jahre lang an den Details zu feilen.