Pépin's test

Description of the test

Let F n = 2 2 n + 1 be the nth Fermat number. Pépin's test states that for n > 0,

The expression 3 ( F n − 1 ) / 2 can be evaluated modulo 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

holds. Then 3 F n − 1 ≡ 1 ( mod F n ) , thus the multiplicative order of 3 modulo F n divides F n − 1 = 2 2 n , which is a power of two. On the other hand, the order does not divide ( F n − 1 ) / 2 , and therefore it must be equal to F n − 1 . In particular, there are at least F n − 1 numbers below F n coprime to F n , and this can happen only if F n is prime.

Necessity: assume that F n is prime. By Euler's criterion,

where ( 3 F n ) is the Legendre symbol. By repeated squaring, we find that 2 2 n ≡ 1 ( mod 3 ) , thus F n ≡ 2 ( mod 3 ) , and ( F n 3 ) = − 1 . As F n ≡ 1 ( mod 4 ) , we conclude ( 3 F n ) = − 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). 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 2016 the smallest untested Fermat number with no known prime factor is F 33 which has 2,585,827,973 digits.