Proof of Pépin's test

Proof

Let $n \ge 1$ and $F = F_n = 2^{2^n} + 1$ , a Fermat number. Put $e = (F - 1)/2 = 2^{2^n - 1}$ . Congruences are modulo $F$ unless stated.

If $F$ is prime, then $3^e \equiv -1$ .

Since $n \ge 1$ , we have $2^n \ge 2$ , so $4$ divides $2^{2^n}$ . Hence $F \equiv 1 \pmod 4$ , and $F \ge 5$ .
Also $2^{2^n} = 4^{2^{n-1}} \equiv 1 \pmod 3$ . Hence $F \equiv 2 \pmod 3$ .
Assume $F$ is prime. Then $F$ and $3$ are distinct odd primes.
By the law of quadratic reciprocity, with Legendre symbols, $\left(\frac{3}{F}\right)\left(\frac{F}{3}\right) = (-1)^{1 \cdot e} = 1$ , because $e$ is even.
The squares modulo $3$ are $0^2 \equiv 0$ , $1^2 \equiv 1$ and $2^2 \equiv 1$ . So $F \equiv 2$ is a quadratic nonresidue modulo $3$ , and $\left(\frac{F}{3}\right) = -1$ .
By step 4, $\left(\frac{3}{F}\right) = -1$ .
By Euler's criterion, $3^e \equiv \left(\frac{3}{F}\right) = -1 \pmod F$ .

If $3^e \equiv -1$ , then $F$ is prime.

Assume $3^e \equiv -1 \pmod F$ . A common divisor of $3$ and $F$ divides $3^e$ and $3^e + 1$ , hence divides $1$ . So $\gcd(3, F) = 1$ .
So the class $[3]$ lies in the group $G = (\Z/F\Z)^\times$ of units, by the units of Z/nZ. Let $r$ be its order in $G$ .
Squaring the assumption gives $3^{2e} = 3^{F-1} \equiv 1$ . By the order criterion, $r$ divides $F - 1 = 2^{2^n}$ . So $r = 2^j$ with $0 \le j \le 2^n$ .
If $j < 2^n$ , then $r$ divides $e = 2^{2^n - 1}$ , so $3^e \equiv 1$ . With $3^e \equiv -1$ this gives $F \mid 2$ , which is false since $F \ge 5$ .
So $r = 2^{2^n} = F - 1$ .
The order of an element divides the order of the group. The group $G$ has $\varphi(F)$ elements, by the order of the units group. So $F - 1 \le \varphi(F)$ .
By the definition of Euler's totient function, $\varphi(F)$ counts integers $k$ with $1 \le k \le F$ coprime to $F$ . The integer $k = F$ is not coprime to $F > 1$ , so $\varphi(F) \le F - 1$ .
Hence $\varphi(F) = F - 1$ , and each $k$ with $1 \le k \le F - 1$ is coprime to $F$ .
If $d$ were a divisor of $F$ with $1 < d < F$ , then $\gcd(d, F) = d > 1$ , contrary to step 15. So $F$ is prime.

Idea

If $F_n$ is prime, quadratic reciprocity shows that $3$ is not a square modulo $F_n$ , and Euler's criterion turns this into the congruence. Conversely, the congruence makes the order of $3$ equal to $F_n - 1$ . Only a prime modulus has that many units.

Tag	`5F18K7X480`
URI	`m2://5F18K7X480`
Kind	proof
Writing	W0 stub
MSC	11Y11
Proves	Pépin's test
Uses	Fermat number, Congruence modulo n, Prime number, Legendre symbol, Quadratic residue, Law of quadratic reciprocity, Euler's criterion, Units of Z/nZ are the residues coprime to n, Group of units of a ring, g to the n equals 1 iff the order divides n, Order of an element divides the order of the group, Order of the group of units of Z/nZ is Euler's totient, Euler's totient function
Changed	4 November 2026

Tag

5F18K7X480

URI

m2://5F18K7X480

Kind

proof

Writing

W0 stub

MSC

11Y11

Proves

Pépin's test

Uses

Fermat number, Congruence modulo n, Prime number, Legendre symbol, Quadratic residue, Law of quadratic reciprocity, Euler's criterion, Units of Z/nZ are the residues coprime to n, Group of units of a ring, g to the n equals 1 iff the order divides n, Order of an element divides the order of the group, Order of the group of units of Z/nZ is Euler's totient, Euler's totient function

Changed

4 November 2026

Proof of Pépin's test

Proof

Idea

Reading path

Where this leads

Further reading

What this page needs for W1

What links here