| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Pépin's test"
m |
(Adding to new subcategory) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 6: | Line 6: | ||
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". | 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 [[ | + | Pépin's test can also be used for proving the primality of other numbers, like the [[Generalized Fermat number]]s <math>F_{n,2} = 4^{3^n}+2^{3^n}+1</math> with k = 5 instead of k = 3. |
==The Maths== | ==The Maths== | ||
| Line 25: | Line 25: | ||
And Lucas pointed out that the proof of sufficiency of Pépin's test followed from his fundamental theorem, with <math>\alpha = 5 \ , \ \beta = 1</math>. | And Lucas pointed out that the proof of sufficiency of Pépin's test followed from his fundamental theorem, with <math>\alpha = 5 \ , \ \beta = 1</math>. | ||
| − | The Fermat numbers <math>\ F_7</math>, <math>\ F_8</math>, <math>\ F_{13}</math>, <math>\ F_{14}</math>, <math>\ F_{17}</math>, <math>\ F_{20}</math>, <math>\ F_{22}</math>, <math>\ F_{24}</math> and <math>\ 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>\ F_{20}</math>, and <math>\ F_{24}</math>. The smallest Fermat number with unknown primality status is the enormous <math>\ F_{33}</math> with | + | The Fermat numbers <math>\ F_7</math>, <math>\ F_8</math>, <math>\ F_{13}</math>, <math>\ F_{14}</math>, <math>\ F_{17}</math>, <math>\ F_{20}</math>, <math>\ F_{22}</math>, <math>\ F_{24}</math> and <math>\ 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>\ F_{20}</math>, and <math>\ F_{24}</math>. The smallest Fermat number with unknown primality status is the enormous <math>\ F_{33}</math> with {{Num|2585827973}} decimal digits. Unfortunately, performing Pépin's test on this number on our fastest computers would take centuries to run to completion! |
==External links== | ==External links== | ||
| − | *[ | + | *[[Wikipedia:Pépin's test|Pépin's test]] |
| − | [[Category: | + | |
| + | [[Category:Deterministic primality tests]] | ||
Latest revision as of 01:16, 11 August 2024
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 Generalized 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!
