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 for a French mathematician, Théophile Pépin.
Description of the test
Let be the nth Fermat number. Pépin's test states that for n > 0,
- is prime if and only if
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.
Proof of correctness
Sufficiency: assume that the congruence
holds. Then , 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 . In particular, there are at least numbers below coprime to , and this can happen only if is prime.
Necessity: assume that is prime. By Euler's criterion,
Historical Pépin tests
Because of the sparsity of the Fermat numbers, the Pépin test has only been run seven times (on Fermat numbers whose primality statuses were not already known). Mayer, Papadopoulos and Crandall speculate that in fact, because of the size of the still undetermined Fermat numbers, it will take decades before technology allows any more Pépin tests to be run. As of 2012[update] the smallest untested Fermat number with no known prime factor is which has 2,585,827,973 digits.
|Year||Provers||Fermat number||Pépin test result||Factor found later?|
|1905||Morehead & Western||composite||Yes (1970)|
|1909||Morehead & Western||composite||Yes (1980)|
|1961||Selfridge & Hurwitz||composite||Yes (2010)|
|1987||Buell & Young||composite||No|
|1993||Crandall, Doenias, Norrie & Young||composite||Yes (2010)|
|1999||Mayer, Papadopoulos & Crandall||composite||No|
- Conjecture 4. Fermat primes are finite - Pepin tests story, according to Leonid Durman
- Wilfrid Keller: Fermat factoring status
- Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos, The twenty-fourth Fermat number is composite (2003)
- P. Pépin, Sur la formule , Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329–333.