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

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 | Quelltext bearbeiten]

Der Test beruht auf folgendem Satz:

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

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 | Quelltext bearbeiten]

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

.

Aufgrund des quadratischen Reziprozitätsgesetzes gilt

.

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.

“: Nehmen wir umgekehrt an, dass

gilt, so folgt durch Quadrieren

.

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 | Quelltext 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 | Quelltext bearbeiten]

  • Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin u. a. 2006, ISBN 3-540-34283-4, S. 71–72.
  • Théophile Pépin: Sur la formule . In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Bd. 85, 1877, ISSN 0001-4036, S. 329–333

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Historische Anmerkungen sind enthalten in John H. Jaroma: Equivalence of Pepin’s and the Lucas-Lehmer Tests. In: European Journal of Pure & Applied Mathematics. Bd. 2, Nr. 3, 2009, ISSN 1307-5543, S. 352–360. Statt der Basis 3 kann man auch andere Basen verwenden, z. B. 5 und 10.