Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Pépin's test"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
m
Line 4: Line 4:
 
Pépin's test has been proven by French Father Pépin in 1877.
 
Pépin's test has been proven by French Father Pépin in 1877.
  
In his famous book about [[Edouard Lucas]] (page 101), HC Williams says: "The test that we today call Pépin's test is actually [[Proth's theorem|Proth's test]] with a proof provided by Lucas".
+
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 theorem|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 number]]s <math>F_{n,2} = 4^{3^n}+2^{3^n}+1</math> with k = 5 instead of k = 3.
 
Pépin's test can also be used for proving the primality of other numbers, like the [[Generalised Fermat number]]s <math>F_{n,2} = 4^{3^n}+2^{3^n}+1</math> with k = 5 instead of k = 3.

Revision as of 14:32, 17 February 2019

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