Pépin's test (sufficiency)
ProvedFamousTheorems.pepin_testPépin's test (sufficiency). Let be the -th Fermat number. If
then is prime.
Pépin's test is the standard deterministic primality test for Fermat numbers. By quadratic reciprocity the converse also holds for , but only the certifying direction is stated here. It has been used to prove , and composite and to confirm prime.
Formalization note. Mathlib's Nat.pepin_primality. Nat.fermatNumber n is and the congruence is stated in ZMod (Nat.fermatNumber n). The exponent equals . The converse (necessity) is not part of this statement.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem pepin_test (n : ℕ) (h : (3 : ZMod n.fermatNumber) ^ 2 ^ (2 ^ n - 1) = -1) : n.fermatNumber.Prime := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.pepin_primality`. Proof here reduces to that Mathlib result.