# Pépin's test

(Redirected from Pepin's test)

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 ${\displaystyle F_{n}=2^{2^{n}}+1}$ be the nth Fermat number. Pépin's test states that for n > 0,

${\displaystyle F_{n}}$ is prime if and only if ${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {F_{n}}}.}$

The expression ${\displaystyle 3^{(F_{n}-1)/2}}$ can be evaluated modulo ${\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, for example 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48 (sequence A129802 in the OEIS).

## Proof of correctness

Sufficiency: assume that the congruence

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$

holds. Then ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$, thus the multiplicative order of 3 modulo ${\displaystyle F_{n}}$ divides ${\displaystyle F_{n}-1=2^{2^{n}}}$, which is a power of two. On the other hand, the order does not divide ${\displaystyle (F_{n}-1)/2}$, and therefore it must be equal to ${\displaystyle F_{n}-1}$. In particular, there are at least ${\displaystyle F_{n}-1}$ numbers below ${\displaystyle F_{n}}$ coprime to ${\displaystyle F_{n}}$, and this can happen only if ${\displaystyle F_{n}}$ is prime.

Necessity: assume that ${\displaystyle F_{n}}$ is prime. By Euler's criterion,

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$,

where ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ is the Legendre symbol. By repeated squaring, we find that ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, thus ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$, and ${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$. As ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$, we conclude ${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$ from the law of quadratic reciprocity.

## Historical Pépin tests

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 decades before technology allows any more Pépin tests to be run.[4] As of 2012 the smallest untested Fermat number with no known prime factor is ${\displaystyle F_{33}}$ which has 2,585,827,973 digits.

Year Provers Fermat number Pépin test result Factor found later?
1905 Morehead & Western ${\displaystyle F_{7}}$ composite Yes (1970)
1909 Morehead & Western ${\displaystyle F_{8}}$ composite Yes (1980)
1952 Robinson ${\displaystyle F_{10}}$ composite Yes (1953)
1960 Paxson ${\displaystyle F_{13}}$ composite Yes (1974)
1961 Selfridge & Hurwitz ${\displaystyle F_{14}}$ composite Yes (2010)
1987 Buell & Young ${\displaystyle F_{20}}$ composite No
1993 Crandall, Doenias, Norrie & Young ${\displaystyle F_{22}}$ composite Yes (2010)
1999 Mayer, Papadopoulos & Crandall ${\displaystyle F_{24}}$ composite No

## References

• P. Pépin, Sur la formule ${\displaystyle 2^{2^{n}}+1}$, Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329–333.