The Lucas–Lehmer primality test
ProvedFamousTheorems.lucas_lehmer_sufficiencyThe Lucas\u2013Lehmer test. For , the Mersenne number is prime if the Lucas\u2013Lehmer sequence , satisfies . The test decides primality of in modular squarings, with no trial division and no randomness — astonishingly cheap for numbers of this size. That efficiency is why every record-holding largest known prime for decades has been a Mersenne prime, and it is the computational core of the GIMPS distributed search. The underlying reason is that the recurrence tracks powers of in a quadratic extension, and the congruence detects that this element has the order forced by being prime. Lucas devised the method in 1878 and Lehmer simplified it in 1930. Formalization note. This is the sufficiency direction: the congruence implies primality. The result is Mathlib's lucas_lehmer_sufficiency.
import Mathlib
namespace FamousTheorems
universe u_1 u_2 u_3 u_4 u_5 u_6 u_7 u_8 u_9 u_10 u_11 u_12 u_13 u_14 u_15 u_16 u_17 u_18 u_19 u_20 u_21 u_22 u_23 u_24 u_25
open Filter Set Topology DirectSum
theorem lucas_lehmer_sufficiency :
∀ (p : ℕ), 1 < p → LucasLehmerTest p → Nat.Prime (mersenne p) := by sorry
end FamousTheorems