Benutzer:Boobarkee/Euler: 2147483647 ist eine Primzahl

Leonhard Euler schrieb einen Brief an Daniel Bernoulli, der 1772 veröffentlicht wurde. Unter anderem gibt er in diesem Brief sehr knapp und äußerst bescheiden eine Sensation bekannt: Die 31. Mersenne-Zahl M₃₁ = 2³¹-1 = 2147483647 ist eine Primzahl.

„Die größte Primzahl, die wir kennen, ist zweifelsohne 2³¹-1 = 2147483647, von der Fermat bereits überprüft hat, dass sie eine Primzahl ist; ich konnte das nun ebenfalls beweisen; denn diese Zahl läßt nur Primteiler der beiden Formen 248n +1 und 248n +63 zu, ich habe alle Primzahlen dieser beiden Bauarten bis 46339 [denn falls M₃₁ nicht prim ist, muss sie einen Teiler kleiner als ihre Quadratwurzel besitzen] überprüft, keine von ihnen hat sich als ein Teiler erwiesen.“

– Leonhard Euler

Ausgangssituation

Grundsätzlich war bekannt, dass jeder Teiler m von n auch einen Teiler 2^m-1 von 2ⁿ-1 liefert. Insbesondere kann eine Mersenne-Zahl M_n nur dann eine Primzahl sein, wenn n prim ist. Die Umkehrung gilt nicht allgemein, denn M₁₁ = 2047 ist das Produkt aus 23 und 89.

Fermat konnte bereits folgende Aussage beweisen: Sind p und q zwei ungerade Primzahlen und teilt p die Zahl M_q, so muss gelten $p\equiv 1{\bmod {q}}$ (d. h., p ist um 1 größer als ein ganzzahliges Vielfaches von q).

Eulers Vorgehen

Euler konnte ergänzend zu Fermats Hilfssatz zeigen, dass unter den genannten Voraussetzungen die Zahl 2 ein quadratischer Rest modulo p sein muss, d. h., es gibt eine ganze Zahl z mit $z^{2}\equiv 2{\bmod {p}}$. Nach dem 2. Ergänzungssatz zum Quadratischen Reziprozitätsgesetz ist 2 genau dann ein quadratischer Rest modulo p, wenn $p\equiv \pm 1{\pmod {8}}$ gilt, d. h., p unterscheidet sich nur um 1 von einem Vielfachen von 8.

Beide Aussagen, die von Fermat zusammen mit der von Euler, bedeuten im Fall q=31, dass ein potentieller Primteiler p von M₃₁ eine der beiden Formen 248n+1 und 248n+63 haben muss (248 ist das Produkt von 31 und 8). Im Bereich von 1 und 46339 gibt es genau 374 Zahlen von dieser Form. Darunter finden sich 84 Primzahlen, durch die Euler M₃₁ dividieren musste. (Unerwarteter Weise verteilen sich diese 84 Primzahlen gleichmäßig: 42 ergeben Rest 1 modulo 248, die anderen 42 Rest 63.) Die 290 zusammengesetzten Zahlen weisen zumeist einen relativ kleinen kleinsten Primfaktoren auf; der größte unter den kleinsten ist 167, das Gros ist ein- oder zweistellig.

Letzteres hat ein kleines ARIBAS-Programm ergeben, das Eulers Vorgehen entsprechend obigen Zitats nachzuvollziehen versucht. Quellcode und Ergebnisse befinden sich hier.

Ohne Eulers Beobachtung, dass 2 ein quadratischer Rest modulo p sein muss, wären 747 ungerade potentielle Teiler abzuarbeiten gewesen; davon sind 157 prim; bei den anderen reichen die kleinsten Primfaktoren bis 199 hinauf. Insgesamt ergibt sich somit etwa der zu erwartende etwa doppelt so große Rechenaufwand (1 Kandidat auf ein Intervall der Länge 62 (die geraden Kandidaten bleiben unberücksichtigt), statt 2 Kandidaten auf ein Intervall der Länge 248).