Inmathematics,Pépin's test is aprimality test, which can be used to determine whether aFermat number isprime. It is a variant ofProth's test. The test is named after a French mathematician,Théophile Pépin.

Let${\displaystyle F_n=2^{2^n}+1}$ be thenth Fermat number. Pépin's test states that forn > 0,

${\displaystyle F_n}$ is prime if and only if${\displaystyle 3^{(F_n-1)/2}\equiv -1(\mathrm{mod}{F}_n).}$

The expression${\displaystyle 3^{(F_n-1)/2}}$ can be evaluated modulo${\displaystyle F_n}$ byrepeated squaring. This makes the test a fastpolynomial-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, ... (sequenceA129802 in theOEIS).

The primes in the above sequence are calledElite 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, ... (sequenceA102742 in theOEIS)

For integerb > 1, baseb may be used if and only if only a finite number of Fermat numbersF_n satisfies that${\displaystyle \left(\frac{b}{F_n}\right)=1}$, where${\displaystyle \left(\frac{b}{F_n}\right)}$ is theJacobi symbol.

In fact, Pépin's test is the same as theEuler-Jacobi test for Fermat numbers, since the Jacobi symbol${\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.

Sufficiency: assume that the congruence

${\displaystyle 3^{(F_n-1)/2}\equiv -1(\mathrm{mod}{F}_n)}$

holds. Then${\displaystyle 3^{F_n-1}\equiv 1(\mathrm{mod}{F}_n)}$, thus themultiplicative 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. ByEuler's criterion,

${\displaystyle 3^{(F_n-1)/2}\equiv \left(\frac{3}{F_n}\right)(\mathrm{mod}{F}_n)}$,

where${\displaystyle \left(\frac{3}{F_n}\right)}$ is theLegendre symbol. By repeated squaring, we find that${\displaystyle 2^{2^n}\equiv 1(\mathrm{mod}3)}$, thus${\displaystyle F_n\equiv 2(\mathrm{mod}3)}$, and${\displaystyle \left(\frac{F_n}{3}\right)=-1}$.As${\displaystyle F_n\equiv 1(\mathrm{mod}4)}$, we conclude${\displaystyle \left(\frac{3}{F_n}\right)=-1}$ from thelaw 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.^[4]

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

• P. Pépin,Sur la formule${\displaystyle 2^{2^n}+1}$,Comptes rendus de l'Académie des Sciences de Paris 85 (1877), pp. 329–333.

• The Prime Glossary: Pepin's test

• Primality tests