Pépin test

The Pépin test is a prime number test for Fermat numbers . It checks for natural numbers of the form

${\displaystyle F_{k}:=2^{2^{k}}+1}$

are prime or not. The basis for the Pépin test is the work of Théophile Pépin (1826–1904), François Proth (1852–1879) and Édouard Lucas .

functionality

The test is based on the following sentence:

F _k is a prime number for k ≥ 1 if and only if the congruence

${\displaystyle 3^{(F_{k}-1)/2}\equiv -1\mod F_{k}}$

is satisfied.

Since F ₀ = 3, the theorem does not hold for k = 0 . For k = 1 , F _k = 5 and 3 ² = 9 ≡ −1 mod 5. To calculate for larger k , the modulo command is used in the intermediate steps, as illustrated in the example below.

Proof of the theorem

“ ”: If the Fermat number F _{k is} prime for a k ≥ 1 , then according to Euler's criterion for the Legendre symbol the congruence applies ${\displaystyle \Rightarrow }$

${\displaystyle 3^{(F_{k}-1)/2}\equiv \left({\frac {3}{F_{k}}}\right)\mod F_{k}}$ .

Due to the quadratic reciprocity law, the following applies

${\displaystyle \left({\frac {3}{F_{k}}}\right)=\left({\frac {F_{k}}{3}}\right)=\left({\frac {2}{3}}\right)=-1}$ .

Here the congruences F _k ≡ 1 mod 4 and F _k ≡ 2 mod 3 ( to be shown with induction ) are used. The proof is thus provided in one direction.

" ": Let's assume conversely that ${\displaystyle \Leftarrow }$

${\displaystyle 3^{(F_{k}-1)/2}\equiv -1\mod F_{k}}$

holds, it follows by squaring

${\displaystyle 3^{F_{k}-1}\equiv 1\mod F_{k}}$ .

According to the improved Lucas test, it follows that F _{k is} prime.

The application of the improved Lucas test is particularly easy in this case, since F _k - 1 has only one prime divisor, namely 2.

example

As an example, we use the Pépin test to show that F ₃ = 2 ⁸ + 1 = 257 is a prime number. We compute 3 ¹²⁸ mod 257 step by step and get 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.

literature

• Paulo Ribenboim : The world of prime numbers. Secrets and Records. Springer, Berlin et al. 2006, ISBN 3-540-34283-4 , pp. 71-72.
• Théophile Pépin: Sur la formule . ${\displaystyle 2^{2^{n}}+1}$In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Vol. 85, 1877, ISSN  0001-4036 , pp. 329-333

Individual evidence

1. ↑ Historical notes are contained in John H. Jaroma: Equivalence of Pepin's and the Lucas-Lehmer Tests. In: European Journal of Pure & Applied Mathematics. Vol. 2, No. 3, 2009, ISSN  1307-5543 , pp. 352-360. Instead of base 3, you can also use other bases, e.g. B. 5 and 10.