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.
be the nth Fermat number.
Pépin's test states that for n > 0, The expression
can be evaluated modulo
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: The primes in the above sequence are called Elite primes, they are: For integer b > 1, base b may be used if and only if only a finite number of Fermat numbers Fn satisfies that
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
is −1, i.e. there are no Fermat numbers which are Euler-Jacobi pseudoprimes to these bases listed above.
Sufficiency: assume that the congruence holds.
( mod
, thus the multiplicative order of 3 modulo
divides
, which is a power of two.
On the other hand, the order does not divide
, and therefore it must be equal to
coprime to
Necessity: assume that
By Euler's criterion, where
is the Legendre symbol.
By repeated squaring, we find that
from the law of quadratic reciprocity.
Because of the sparsity of the Fermat numbers, the Pépin test has only been run eight times (on Fermat numbers whose primality statuses were not already known).
[1][2][3] Mayer, Papadopoulos and Crandall speculate that in fact, because of the size of the still undetermined Fermat numbers, it will take considerable advances in technology before any more Pépin tests can be run in a reasonable amount of time.