There are infinitely many Fermat pseudoprimes (Cipolla)
ProvedFamousTheorems.infinitely_many_fermat_pseudoprimesThere are infinitely many Fermat pseudoprimes (Cipolla). Let . For every there is an that is a Fermat pseudoprime to base : is composite and .
Fermat's little theorem says that every prime satisfies when . Cipolla showed in 1904 that the converse fails infinitely often, so the Fermat test alone cannot certify primality. This led to the Miller–Rabin test and to the study of Carmichael numbers.
Formalization note. Mathlib's Nat.exists_infinite_pseudoprimes. Nat.FermatPsp n b means n ∣ b ^ (n - 1) - 1, with n not prime and 1 < n. The statement is the unboundedness form of "infinitely many".
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem infinitely_many_fermat_pseudoprimes {b : ℕ} (hb : 1 ≤ b) (m : ℕ) : ∃ n : ℕ, n.FermatPsp b ∧ m ≤ n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.exists_infinite_pseudoprimes`. Proof here reduces to that Mathlib result.