Pépin-Test

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

Der Test beruht auf folgendem Satz:

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

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

erfüllt ist.<ref>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, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|1307-5543|0}}{{#ifeq:1|0|[!] }}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=1307-5543}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, S. 352–360. Statt der Basis 3 kann man auch andere Basen verwenden, z. B. 5 und 10.</ref>

Da F₀ = 3 ist, gilt der Satz nicht für k = 0. Für k = 1 ist F_k = 5 und es gilt 3² = 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

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

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

Aufgrund des quadratischen Reziprozitätsgesetzes gilt

<math>\left(\frac{3}{F_k}\right) = \left(\frac{F_k}{3}\right) = \left(\frac{2}{3}\right) = -1</math> .

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

„<math>\Leftarrow</math>“: Nehmen wir umgekehrt an, dass

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

gilt, so folgt durch Quadrieren

<math>3^{F_k-1} \equiv 1 \mod F_k</math> .

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

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

Beispiel

Als Beispiel zeigen wir mit Hilfe des Pépin-Tests, dass F₃ = 2⁸ + 1 = 257 eine Primzahl ist. Wir berechnen 3¹²⁸ mod 257 schrittweise und erhalten 3¹²⁸ ≡ −1 mod 257:

3⁸ = 6561 ≡ –121 mod 257,
→ 3¹⁶ ≡ (–121)² ≡ –8 mod 257,
→ 3³² ≡ (–8)² ≡ 64 mod 257,
→ 3⁶⁴ ≡ 64² ≡ –16 mod 257,
→ 3¹²⁸ ≡ (–16)² = 256 ≡ –1 mod 257.

Literatur

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 <math>2^{2^n}+1</math>. In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Bd. 85, 1877, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0001-4036|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0001-4036}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, S. 329–333

Einzelnachweise