Mersenne-Primzahl-Prüfer

Mersenne-Primzahl-Prüfer

Willkommen beim Mersenne-Primzahl-Prüfer, einem interaktiven Tool, das testet, ob \(2^p - 1\) eine Mersenne-Primzahl für einen beliebigen Exponenten \(p\) bis zu 5000 ist. Das Tool führt den berühmten Lucas-Lehmer-Primzahltest aus, zeigt einen animierten Iterationsverlauf der Rekursion \(S_i = S_{i-1}^2 - 2 \pmod{M_p}\), visualisiert das binäre Bitmuster (ein charakteristisches Merkmal jeder Mersenne-Zahl) und ordnet dem Ergebnis – falls es prim ist – die entsprechende gerade vollkommene Zahl über den Satz von Euklid-Euler zu.

Was ist eine Mersenne-Primzahl?

Eine Mersenne-Zahl ist eine Zahl der Form \(M_p = 2^p - 1\). Wenn \(M_p\) selbst prim ist, wird sie als Mersenne-Primzahl bezeichnet. Der Name ehrt Marin Mersenne (1588–1648), den französischen Mönch, der die frühen Fälle katalogisierte und vermutete, welche Exponenten bis 257 Primzahlen ergaben – eine Liste, die sich zwar als teilweise falsch herausstellte, aber drei Jahrhunderte der Forschung einläutete.

Die ersten Mersenne-Primzahlen in der Reihenfolge:

• \(M_2 = 3\)
• \(M_3 = 7\)
• \(M_5 = 31\)
• \(M_7 = 127\)
• \(M_{13} = 8{,}191\)
• \(M_{17} = 131{,}071\)
• \(M_{19} = 524{,}287\)
• \(M_{31} = 2{,}147{,}483{,}647\) (1772 von Euler entdeckt – 104 Jahre lang die größte bekannte Primzahl)

Stand 2024 sind genau 52 Mersenne-Primzahlen bekannt. Der aktuelle Rekord ist \(M_{136{,}279{,}841}\), entdeckt im Oktober 2024 durch das GIMPS-Projekt für verteiltes Rechnen – eine Zahl mit 41.024.320 Dezimalstellen.

Der Lucas-Lehmer-Test

Der Grund, warum Mersenne-Primzahlen die Rekordbücher dominieren, ist ein spezialisierter, extrem schneller Primzahltest, der von Édouard Lucas (1878) entdeckt und von Derrick Lehmer (1930) vereinfacht wurde:

Der Test erfordert nur \(p-2\) modulare Quadrierungen – etwa \(O(p^3)\) Bit-Operationen mit Schulmultiplikation oder \(O(p^2 \log p \log\log p)\) mit FFT. Vergleichen Sie dies mit universellen Primzahltests bei Zahlen von der Größe eines \(M_p\) (Millionen von Stellen), die völlig undurchführbar wären. Die Lucas-Lehmer-Abkürzung ist das, was die Suche nach Mersenne-Primzahlen überhaupt erst ermöglicht.

Warum muss \(p\) prim sein?

Wenn \(p = a \cdot b\) mit \(a, b > 1\), zeigt eine klassische Identität, dass \(2^a - 1\) ein Teiler von \(2^{ab} - 1\) ist:

Wenn der Exponent also zusammengesetzt ist, ist \(M_p\) automatisch zusammengesetzt. Die Umkehrung ist falsch: Dass \(p\) prim ist, garantiert nicht, dass \(M_p\) prim ist. Zum Beispiel ist \(p = 11\) prim, aber \(M_{11} = 2047 = 23 \times 89\).

Mersenne-Primzahlen und vollkommene Zahlen (Euklid-Euler)

Euklid beobachtete um 300 v. Chr., dass wenn \(2^p - 1\) prim ist, dann \(2^{p-1}(2^p - 1)\) eine vollkommene Zahl ist – eine Zahl, die gleich der Summe ihrer echten Teiler ist. Euler bewies später die Umkehrung: Jede gerade vollkommene Zahl entsteht auf diese Weise.

Das Finden einer neuen Mersenne-Primzahl erzeugt also sofort eine neue vollkommene Zahl. Die ersten vier geraden vollkommenen Zahlen sind 6, 28, 496 und 8128 – bekannt seit der Antike. Ob eine ungerade vollkommene Zahl existiert, bleibt ein seit mehr als 2.300 Jahren ungelöstes Problem.

Das binäre Bitmuster

Jede Mersenne-Zahl hat eine einzigartig klare Binärdarstellung: \(2^p\) ist binär eine \(1\) gefolgt von \(p\) Nullen, daher besteht \(2^p - 1\) aus genau \(p\) aufeinanderfolgenden 1-Bits:

Deshalb visualisiert das Tool jedes Bit als eigene Kachel – das Bitmuster ist die visuelle Signatur einer Mersenne-Zahl, unabhängig davon, ob die Zahl prim ist.

So verwenden Sie diesen Rechner

1. Geben Sie einen Exponenten \(p\) ein: jede positive ganze Zahl von 1 bis 5.000.
2. Klicken Sie auf Prüfen: Das Tool prüft zuerst, ob \(p\) prim ist; falls nicht, wird erklärt, warum \(M_p\) zusammengesetzt sein muss.
3. Für primes \(p\): Die Lucas-Lehmer-Rekursion führt \(p - 2\) Iterationen modulo \(M_p\) durch.
4. Ergebnisse erkunden: Urteils-Banner, 6-zeiliger Iterationsverlauf (mit "..." für ausgelassene Zwischenschritte bei großem \(p\)), Dezimal- und Binärform von \(M_p\) sowie die vollkommene Zahl nach Euklid-Euler, falls zutreffend.

Die ersten zwölf bekannten Mersenne-Primzahlen

Das GIMPS-Projekt

Die Great Internet Mersenne Prime Search (GIMPS), 1996 von George Woltman ins Leben gerufen, ist ein Projekt für verteiltes Rechnen, bei dem Freiwillige CPU-Zeit spenden, um Lucas-Lehmer-Tests an Exponenten-Kandidaten durchzuführen. Stand 2024 wurde jede Mersenne-Primzahl seit M_35 = M_{1398269} (1996) durch GIMPS entdeckt. Ein einzelner Lucas-Lehmer-Test an der modernen Grenze (Exponenten nahe \(10^8\)) dauert Wochen auf GPU-Systemen.

Wissenswertes über Mersenne-Primzahlen

• \(M_{31} = 2{,}147{,}483{,}647\) ist die größte 32-Bit-Ganzzahl mit Vorzeichen – das berühmte \(\texttt{INT\_MAX}\) in C. Der Wert ist \(2^{31} - 1\), weil eine 32-Bit-Ganzzahl im Zweierkomplement 31 Betragsbits hat; dass diese Zahl zugleich prim ist, ist reiner Zufall.
• Es gibt Lücken unbekannter Größe zwischen aufeinanderfolgenden Mersenne-Primzahlen. Es ist nicht bekannt, ob es unendlich viele Mersenne-Primzahlen gibt – die Lenstra-Pomerance-Wagstaff-Vermutung sagt voraus, dass sie existieren und etwa wie \(e^\gamma \log_2 p\) wachsen.
• Im Jahr 2008 verlieh die Electronic Frontier Foundation 100.000 US-Dollar an den ersten Entdecker einer Primzahl mit 10 Millionen Stellen. Der Preis ging an das GIMPS-Team der UCLA für \(M_{43112609}\). Ein Preis von 150.000 US-Dollar ist weiterhin für die erste Primzahl mit 100 Millionen Stellen ausgeschrieben.
• Da jede Mersenne-Primzahl eine vollkommene Zahl ergibt, hat die Menschheit genau 52 gerade vollkommene Zahlen dokumentiert (entsprechend den 52 bekannten Mersenne-Primzahlen).

Häufig gestellte Fragen

Was ist eine Mersenne-Primzahl?

Eine Mersenne-Primzahl ist eine Primzahl der Form \(2^p - 1\), wobei \(p\) ebenfalls prim ist. Die ersten sind 3, 7, 31, 127 und 8.191. Stand 2024 sind 52 Mersenne-Primzahlen bekannt; die größte bekannte Primzahl (\(M_{136{,}279{,}841}\)) ist eine Mersenne-Primzahl mit über 41 Millionen Stellen.

Wie funktioniert der Lucas-Lehmer-Test?

Für einen Primzahlexponenten \(p \geq 3\) definiere \(S_0 = 4\) und \(S_i = S_{i-1}^2 - 2 \pmod{M_p}\). Die Mersenne-Zahl \(M_p = 2^p - 1\) ist genau dann prim, wenn \(S_{p-2} \equiv 0 \pmod{M_p}\). Der Test läuft in \(p - 2\) Iterationen ab, jede eine einzige modulare Quadrierung.

Warum muss \(p\) prim sein?

Wenn \(p = ab\) ist und beide Faktoren größer als 1 sind, dann ist \(2^p - 1\) durch \(2^a - 1\) (und durch \(2^b - 1\)) teilbar, sodass \(M_p\) zusammengesetzt ist. Die Umkehrung gilt nicht: Dass \(p\) prim ist, bedeutet nicht zwangsläufig, dass \(M_p\) prim ist. Zum Beispiel ist \(p = 11\) prim, aber \(M_{11} = 2047 = 23 \times 89\) ist zusammengesetzt.

Was ist die Verbindung zwischen Mersenne-Primzahlen und vollkommenen Zahlen?

Der Satz von Euklid-Euler besagt, dass jede gerade vollkommene Zahl die Form \(2^{p-1}(2^p - 1)\) hat, wobei \(2^p - 1\) eine Mersenne-Primzahl ist. Jede Mersenne-Primzahl erzeugt genau eine gerade vollkommene Zahl, und jede gerade vollkommene Zahl stammt von einer Mersenne-Primzahl ab. Ob ungerade vollkommene Zahlen existieren, ist eines der ältesten offenen Probleme der Mathematik.

Warum hat \(M_p\) im Binärsystem \(p\) aufeinanderfolgende 1-Bits?

Die Zahl \(2^p\) ist binär eine 1 gefolgt von \(p\) Nullen. Das Subtrahieren von 1 wandelt alle \(p\) nachfolgenden Nullen in 1en um. Somit besteht \(2^p - 1\) binär aus genau \(p\) Einsen – die charakteristische visuelle Signatur jeder Mersenne-Zahl, ob prim oder zusammengesetzt.

Was ist der größte Exponent, den dieses Tool testen kann?

Dieses Tool testet Exponenten bis 5.000, damit die Lucas-Lehmer-Iteration innerhalb einer normalen Webanfrage abgeschlossen werden kann. Für größere Exponenten (einschließlich der GIMPS-Grenze nahe \(10^8\)) ist spezialisierte Software wie Prime95 erforderlich, da ein einzelner Test auf einer modernen GPU Wochen an Rechenzeit beanspruchen kann.

Grundrechenoperationen:

• Absolutwert-Rechner Neu
• Befreundete Zahlen Prüfer Neu
• Visualisierung von Übertrag und Borgen Neu
• Decken- und Bodenrechner Neu
• Gemeinsame Teiler Rechner Beliebt
• Kreuzmultiplikation-Rechner Neu
• Kubik- und Kubikwurzel-Rechner
• Kubikwurzel-Rechner
• Digitale Wurzel Rechner Neu
• In zwei Teile teilen
• Teilbarkeit Test Rechner
• Ägyptischer Multiplikationsrechner Neu
• schaetzungsrechner Neu
• Gerade oder Ungerade Zahl Prüfer Neu
• Teiler-Rechner
• Fibonacci Zahl Prüfer Neu
• Minimum und Maximum Finden
• Die ersten n Stellen von e
• Die ersten n Stellen von Pi
• Goldbachsche Vermutung Verifizierer Neu
• Größter gemeinsamer Teiler Rechner
• Ist es eine Primzahl?
• Rechner für das kleinste gemeinsame Vielfache
• Rechner für schriftliches Addieren und Subtrahieren Neu
• Rechner für schriftliche Division Neu
• Langmultiplikation-Rechner Neu
• Möbius-Funktion-Rechner Neu
• Kopfrechen-Trainer Beliebt
• Mersenne-Primzahl-Prüfer Neu
• Modulo-Rechner Beliebt
• Multiplikationsrechner
• Einmaleins-Generator Neu
• n-te Wurzelrechner - Hohe Präzision
• Zahlenzerlegung Generator Neu
• Stellenanzahl-Rechner Beliebt
• Zahlenmuster Finder Neu
• Reihenfolge der Operationen Rechner (PEMDAS) Neu
• Vollkommene Zahlen prüfen Neu
• Stellenwerttafel-Generator Neu
• Primfaktor-Rechner
• Rechner zur Primfaktorzerlegung
• Quotient- und Rest-Rechner
• Zufalls-Mathematikaufgaben-Generator Beliebt
• Verhältnis Rechner Neu
• Mathe-Rechner für römische Zahlen Neu
• Russische Bauernmultiplikation Neu
• Sprungzählung Generator Neu
• Soroban Abakus Simulator Neu
• Zahlen sortieren Beliebt
• Quadratwurzelrechner
• Summen-Rechner
• Einmaleins-Quiz Neu
• Stückpreis Rechner Neu
• Vedischer Mathematik-Tricks-Rechner Neu