Open main menu

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.

Contents

Description of the testEdit

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.

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  , where   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.

Proof of correctnessEdit

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,

 ,

where   is the Legendre symbol. By repeated squaring, we find that  , thus  , and  . As  , we conclude   from the law of quadratic reciprocity.

Historical Pépin testsEdit

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 2016 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)
1952 Robinson   composite Yes (1953)
1960 Paxson   composite Yes (1974)
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

NotesEdit

ReferencesEdit

  • P. Pépin, Sur la formule  , Comptes rendus de l'Académie des Sciences de Paris 85 (1877), pp. 329–333.

External linksEdit