Pépin's Test

A test for the Primality of Fermat Numbers $F_n=2^{2^n}+1$, with $n\geq 2$ and $k\geq 2$. Then the two following conditions are equivalent:

1. $F_n$ is Prime and $(k/F_n) = -1$, where $(n/k)$ is the Jacobi Symbol,

2. $k^{(F_n-1)/2}\equiv -1\ \left({{\rm mod\ } {F_n}}\right)$.

$k$ is usually taken as 3 as a first test.

See also Fermat Number, Pépin's Theorem

References

Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, p. 62, 1991.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 119-120, 1993.