---
tag: 5F18K7X480
kind: proof
name: Proof of Pépin's test
msc: [11Y11]
proves: 07HXA8KV6F
uses: [0R03B54V4Z, 0TPW25CBN6, 0SN0MAEKYX, 01J8AMV9RS, 0SQDB87Z3T, 085MJS6907, 0M7DEDKSYB, 0GXNHEHQNA, 05THZKR9AN, 0F5QC101Q7, 08V7JHS3QZ, 0S7495H4HM, 0VV04M41AN]
sources:
  - url: https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test
    locator: Proof of correctness
---

## Proof

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

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

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$.
2. Also $2^{2^n} = 4^{2^{n-1}} \equiv 1 \pmod 3$. Hence $F \equiv 2 \pmod 3$.
3. Assume $F$ is [[prime|0SN0MAEKYX]]. Then $F$ and $3$ are distinct odd primes.
4. By the [[law of quadratic reciprocity|085MJS6907]], with [[Legendre symbols|01J8AMV9RS]], $\left(\frac{3}{F}\right)\left(\frac{F}{3}\right) = (-1)^{1 \cdot e} = 1$, because $e$ is even.
5. 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|0SQDB87Z3T]] modulo $3$, and $\left(\frac{F}{3}\right) = -1$.
6. By step 4, $\left(\frac{3}{F}\right) = -1$.
7. By [[Euler's criterion|0M7DEDKSYB]], $3^e \equiv \left(\frac{3}{F}\right) = -1 \pmod F$.

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

8. 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$.
9. So the class $[3]$ lies in the group $G = (\Z/F\Z)^\times$ of [[units|05THZKR9AN]], by [[the units of Z/nZ|0GXNHEHQNA]]. Let $r$ be its order in $G$.
10. Squaring the assumption gives $3^{2e} = 3^{F-1} \equiv 1$. By [[the order criterion|0F5QC101Q7]], $r$ divides $F - 1 = 2^{2^n}$. So $r = 2^j$ with $0 \le j \le 2^n$.
11. 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$.
12. So $r = 2^{2^n} = F - 1$.
13. The [[order of an element divides the order of the group|08V7JHS3QZ]]. The group $G$ has $\varphi(F)$ elements, by [[the order of the units group|0S7495H4HM]]. So $F - 1 \le \varphi(F)$.
14. By the definition of [[Euler's totient function|0VV04M41AN]], $\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$.
15. Hence $\varphi(F) = F - 1$, and each $k$ with $1 \le k \le F - 1$ is coprime to $F$.
16. 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.