nat_least_prime_not_dvd_two
The smallest prime not dividing 2 is 3.
Statement
theorem nat_least_prime_not_dvd_two : nat_least_prime_not_dvd 2 = 3- Source
- Sanity lemma for q(m), arXiv:2610.16562 (The Davenport constant of low-dimensional boxes).
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nat_least_prime_not_dvdq(m): the smallest prime number not dividing m (0 by convention for m = 0, which no prime fails to divide).
The proof, explained
By definition, the least prime not dividing 2 is the infimum of the set of primes that do not divide 2. The proof establishes equality with 3 by antisymmetry, showing both bounds separately. The upper bound holds because 3 is a prime not dividing 2 and therefore belongs to the set. The lower bound holds because any prime not dividing 2 must be at least 3, ruling out 0 and 1 because they are not prime and 2 because it divides 2.
To show that the infimum of the set of primes not dividing 2 equals 3, it suffices to prove that the infimum is at most 3 and at least 3.
Unfolding the definition of nat_least_prime_not_dvd 2 gives the infimum of {p ∈ ℕ | p is prime ∧ ¬ p ∣ 2}. By antisymmetry of partial orders (le_antisymm), establishing equality reduces to establishing the two inequalities: the infimum is at most 3, and 3 is at most the infimum.
uses
le_antisymmunfold nat_least_prime_not_dvd apply le_antisymm
The infimum of the set of primes not dividing 2 is at most 3.
By Nat.sInf_le, the infimum of a set of natural numbers is bounded above by any element of that set. The number 3 belongs to the set because 3 is prime (Nat.prime_three) and 3 does not divide 2 (by numeric computation).
uses
Nat.sInf_le,Nat.prime_three· exact Nat.sInf_le (show 3 ∈ {p | p.Prime ∧ ¬ p ∣ 2} from ⟨Nat.prime_three, by norm_num⟩)
To show that 3 is at most the infimum, it suffices to show that 3 is a lower bound for every prime not dividing 2.
By le_csInf, a number is at most the infimum of a nonempty set if it is less than or equal to every element of the set. The set is nonempty because 3 is an element (since 3 is prime by Nat.prime_three and does not divide 2). Thus, it suffices to show that 3 ≤ p for every prime p not dividing 2.
uses
le_csInf,Nat.prime_three· apply le_csInf (show ({p | p.Prime ∧ ¬ p ∣ 2} : Set ℕ).Nonempty from ⟨3, Nat.prime_three, by norm_num⟩)
Every prime not dividing 2 is at least 3.
Let p be a prime such that p does not divide 2. Suppose for contradiction that 3 ≤ p does not hold, which means p < 3. The only natural numbers strictly less than 3 are 0, 1, and 2. The cases p = 0 and p = 1 are ruled out because neither 0 nor 1 is prime (Nat.not_prime_zero and Nat.not_prime_one). The case p = 2 is ruled out because 2 divides itself (dvd_refl), contradicting the assumption that p does not divide 2. Since all cases lead to a contradiction, we conclude 3 ≤ p.
uses
Nat.not_prime_zero,Nat.not_prime_one,dvd_reflrintro p ⟨hp, hpd⟩ by_contra h push_neg at h interval_cases p · exact Nat.not_prime_zero hp · exact Nat.not_prime_one hp · exact hpd (dvd_refl 2)
le_antisymm- In any partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- For any set of natural numbers, its infimum is less than or equal to any element in the set.
Nat.prime_three- The number 3 is prime.
le_csInf- In a conditionally complete lattice, a is less than or equal to the infimum of a nonempty set s if a is a lower bound for every element of s.
Nat.not_prime_zero- The number 0 is not prime.
Nat.not_prime_one- The number 1 is not prime.
dvd_refl- Divisibility is reflexive: every element divides itself.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem nat_least_prime_not_dvd_two : nat_least_prime_not_dvd 2 = 3 := by unfold nat_least_prime_not_dvd apply le_antisymm · exact Nat.sInf_le (show 3 ∈ {p | p.Prime ∧ ¬ p ∣ 2} from ⟨Nat.prime_three, by norm_num⟩) · apply le_csInf (show ({p | p.Prime ∧ ¬ p ∣ 2} : Set ℕ).Nonempty from ⟨3, Nat.prime_three, by norm_num⟩) rintro p ⟨hp, hpd⟩ by_contra h push_neg at h interval_cases p · exact Nat.not_prime_zero hp · exact Nat.not_prime_one hp · exact hpd (dvd_refl 2)