= Pépin's test
{c}
{title2=$3^{(F_n-1)/2}\equiv-1\pmod{F_n}$}
{wiki}
For $n\geq1$, <Pépin's test> says that the <Fermat number> $F_n$ is a <prime number> exactly when the displayed <modular congruence> holds. <Modular exponentiation> evaluates it by <exponentiation by squaring> without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.<Primality testing: then and now by Carl Pomerance>[slide 14]{ref}
For a proof outline of sufficiency, any <prime factor> $p$ of a passing candidate gives $3$ <multiplicative order> exactly $F_n-1$, a <power of two>: its half-power is $-1$, rather than $1$. <Fermat's little theorem> forces $F_n-1\mid p-1$, so $p\geq F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv5\pmod{12}$; <quadratic reciprocity> and <Euler's criterion> give the required half-power. At $n=1$, the check is $3^2\equiv4=-1\pmod5$.
Back to article page
