Lucas's primality test
ProvedFamousTheorems.lucas_primality_testLucas's primality test. Let be a natural number and . Suppose that and that for every prime dividing . Then is prime.
The hypotheses say that has order exactly in , which forces . Lucas's test (1876, refined by Lehmer) turns a factorisation of into a primality certificate. It is the basis of Pratt certificates, which show that primality is in NP.
Formalization note. Mathlib's lucas_primality. The degenerate cases are handled by the hypotheses: for or they cannot both hold.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem lucas_primality_test (p : ℕ) (a : ZMod p) (ha : a ^ (p - 1) = 1)
(hd : ∀ q : ℕ, q.Prime → q ∣ p - 1 → a ^ ((p - 1) / q) ≠ 1) : p.Prime := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `lucas_primality`. Proof here reduces to that Mathlib result.