Pépin's test

Introduction

Pépin's test is mainly used for proving the primality of Fermat numbers, but it is of no help for finding the factors of such numbers.

Pépin's test has been proven by French Father Pépin in 1877.

In his famous book about Édouard Lucas (page 101), HC Williams says: "The test that we today call Pépin's test is actually Proth's test with a proof provided by Lucas".

Pépin's test can also be used for proving the primality of other numbers, like the Generalised Fermat numbers [math]\displaystyle{ F_{n,2} = 4^{3^n}+2^{3^n}+1 }[/math] with k = 5 instead of k = 3.

The Maths

Pépin's test says: If [math]\displaystyle{ n\gt 0 }[/math], [math]\displaystyle{ F_n = 2^{2^n}+1 }[/math] is a prime if and only if [math]\displaystyle{ \ 3^{(F_n-1)/2} \ \equiv -1 \ \pmod{F_n} }[/math].

Bits of history

Pépin found the following:

If [math]\displaystyle{ F_n = 2^{2^n}+1 }[/math], then [math]\displaystyle{ F_n }[/math] is a prime if and only if [math]\displaystyle{ \ 5^{(F_n-1)/2} \equiv -1 \ \pmod{F_n} }[/math].

Then Lucas noticed that any number a can be used instead of 5 if [math]\displaystyle{ \left({a \atop {F_n}}\right) = -1 }[/math], where [math]\displaystyle{ \left({a \atop p}\right) }[/math] is the Jacobi symbol.

Proth in 1878 mentioned the use of 3 but was unable to provide a complete proof, but Lucas later supplied him with one.

Pépin also noted that this test can also be made into a simple Lucas-like test by defining [math]\displaystyle{ T_i=5^2 }[/math] and [math]\displaystyle{ T_{i+1}=T_i^2 }[/math].

[math]\displaystyle{ \ F_n }[/math] is a prime if and only if [math]\displaystyle{ F_n \ \mid \ T_{2^n-1}+1 }[/math].

And Lucas pointed out that the proof of sufficiency of Pépin's test followed from his fundamental theorem, with [math]\displaystyle{ \alpha = 5 \ , \ \beta = 1 }[/math].

The Fermat numbers [math]\displaystyle{ \ F_7 }[/math], [math]\displaystyle{ \ F_8 }[/math], [math]\displaystyle{ \ F_{13} }[/math], [math]\displaystyle{ \ F_{14} }[/math], [math]\displaystyle{ \ F_{17} }[/math], [math]\displaystyle{ \ F_{20} }[/math], [math]\displaystyle{ \ F_{22} }[/math], [math]\displaystyle{ \ F_{24} }[/math] and [math]\displaystyle{ \ F_{28} }[/math] were all originally proven composite by versions of Pépin's test. At present, there are still no known factors of [math]\displaystyle{ \ F_{20} }[/math], and [math]\displaystyle{ \ F_{24} }[/math]. The smallest Fermat number with unknown primality status is the enormous [math]\displaystyle{ \ F_{33} }[/math] with 2,585,827,973 decimal digits. Unfortunately, performing Pépin's test on this number on our fastest computers would take centuries to run to completion!

External links

• Wikipedia