In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named after a French mathematician, Théophile Pépin.
Description of the test Let F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{n}}+1} be the nth Fermat number. Pépin's test states that for n > 0,
F n {\displaystyle F_{n}} is prime if and only if 3 ( F n − 1 ) / 2 ≡ − 1 ( mod F n ) . {\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}
The expression 3 ( F n − 1 ) / 2 {\displaystyle 3^{(F_{n}-1)/2}} can be evaluated modulo F n {\displaystyle F_{n}} by repeated squaring. This makes the test a fast polynomial-time algorithm. However, Fermat numbers grow so rapidly that only a handful of Fermat numbers can be tested in a reasonable amount of time and space. Other bases may be used in place of 3. These bases are:
3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... (sequence A129802 in the OEIS). The primes in the above sequence are called Elite primes, they are:
3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, ... (sequence A102742 in the OEIS) For integer b > 1, base b may be used if and only if only a finite number of Fermat numbers Fn satisfies that ( b F n ) = 1 {\displaystyle \left({\frac {b}{F_{n}}}\right)=1} , where ( b F n ) {\displaystyle \left({\frac {b}{F_{n}}}\right)} is the Jacobi symbol. In fact, Pépin's test is the same as the Euler-Jacobi test for Fermat numbers, since the Jacobi symbol ( b F n ) {\displaystyle \left({\frac {b}{F_{n}}}\right)} is −1, i.e. there are no Fermat numbers which are Euler-Jacobi pseudoprimes to these bases listed above.
Proof of correctness Sufficiency: assume that the congruence
3 ( F n − 1 ) / 2 ≡ − 1 ( mod F n ) {\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}
… excerpt ends here. Continue reading the full article.
