Pépin-Test

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Pépin-Test ist ein Primzahltest für Fermat-Zahlen. Er prüft, ob natürliche Zahlen der Form

F_k:=2^{2^k}+1

prim sind oder nicht. Grundlage für den Pépin-Test sind Arbeiten von Théophile Pépin (1826 – 1904), François Proth (1852 – 1879) und Édouard Lucas.

Funktionsweise[Bearbeiten]

Der Test beruht auf folgendem Satz:

Fk ist für k ≥ 1 genau dann eine Primzahl, wenn die Kongruenz

3^{(F_k-1)/2} \equiv -1 \mod  F_k

erfüllt ist.[1]

Da F0 = 3 ist, gilt der Satz nicht für k = 0. Für k = 1 ist Fk = 5 und es gilt 32 = 9 ≡ −1 mod 5. Zur Berechnung für größere k verwendet man den modulo-Befehl schon in den Zwischenschritten, wie im untenstehenden Beispiel illustriert wird.

Beweis des Satzes[Bearbeiten]

\Rightarrow“: Ist für ein k ≥ 1 die Fermat-Zahl Fk prim, so gilt nach dem Eulerschen Kriterium für das Legendre-Symbol die Kongruenz

3^{(F_k -1)/2} \equiv \left(\frac{3}{F_k}\right) \mod F_k .

Aufgrund des quadratischen Reziprozitätsgesetzes gilt

\left(\frac{3}{F_k}\right) = \left(\frac{F_k}{3}\right) = \left(\frac{2}{3}\right) = -1 .

Hierbei werden die Kongruenzen Fk ≡ 1 mod 4 und Fk ≡ 2 mod 3 (mit Induktion zu zeigen) benutzt. Damit ist der Beweis in einer Richtung erbracht.

\Leftarrow“: Nehmen wir umgekehrt an, dass

3^{(F_k-1)/2} \equiv -1 \mod  F_k

gilt, so folgt durch Quadrieren

3^{F_k-1} \equiv 1 \mod  F_k .

Nach dem verbesserten Lucas-Test folgt, dass Fk prim ist.

Die Anwendung des verbesserten Lucas-Tests ist in diesem Fall besonders einfach, da Fk – 1 nur einen Primteiler, nämlich die 2, hat.

Beispiel[Bearbeiten]

Als Beispiel zeigen wir mit Hilfe des Pépin-Tests, dass F3 = 28 + 1 = 257 eine Primzahl ist. Wir berechnen 3128 mod 257 schrittweise und erhalten 3128 ≡ −1 mod 257:

38 = 6561 ≡ –121 mod 257,
→ 316 ≡ (–121)2 ≡ –8 mod 257,
→ 332 ≡ (–8)2 = 64 mod 257,
→ 364 ≡ 642 ≡ –16 mod 257,
→ 3128 ≡ (–16)2 = 256 ≡ –1 mod 257.

Literatur[Bearbeiten]

  • Paulo Ribenboim: Die Welt der Primzahlen, Springer Verlag, 1996, S. 71/72
  • T. Pépin, Sur la formule 2^{2^n}+1, Comptes Rendus Acad. Sci. Paris 85, 329 – 333, 1877

Einzelnachweise[Bearbeiten]

  1. Historische Anmerkungen sind enthalten in John H. Jaroma: Equivalence of Pepin’s and the Lucas-Lehmer Tests, European J. of pure and applied mathematics 2, 352 - 360, 2009. Statt der Basis 3 kann man auch andere Basen verwenden, z. B. 5 und 10.