Pépin'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, P. Pépin.

Description of the test

Let $F\_n=2^\{2^n\}+1$ be the "n"th Fermat number. Pépin's test states that if "n" is non-zero,:$F\_n$ is prime if and only if $3^\{(F\_n-1)/2\}equiv-1pmod\{F\_n\}$.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, or 10 OEIS|id=A129802.

Proof of correctness

For one direction, assume that the congruence:$3^\{(F\_n-1)/2\}equiv-1pmod\{F\_n\}$holds. Then $3^\{F\_n-1\}equiv1pmod\{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.

For the other direction, assume that $F\_n$ is prime. By Euler's criterion,:$3^\{(F\_n-1)/2\}equivleft(frac3\{F\_n\}\; ight)pmod\{F\_n\}$,where $left(frac3\{F\_n\}\; ight)$ is the Legendre symbol. By repeated squaring, we find that $2^\{2^n\}equiv1pmod3$, thus $F\_nequiv2pmod3$, and $left(frac\{F\_n\}3\; ight)=-1$.As $F\_nequiv1pmod4$, we conclude $left(frac3\{F\_n\}\; ight)=-1$ from the law of quadratic reciprocity.

References

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

External links

* [http://primes.utm.edu/glossary/page.php?sort=PepinsTest The Prime Glossary: Pepin's test]