AFTD Auto-Formalizing Theoretical Domains

nat_least_prime_not_dvd_two

theoremverified

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.

  1. 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.

    lines 2–3

    uses le_antisymm

      unfold nat_least_prime_not_dvd
      apply le_antisymm
  2. 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).

    line 4

    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⟩)
  3. 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.

    line 5

    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⟩)
  4. 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.

    lines 6–12

    uses Nat.not_prime_zero, Nat.not_prime_one, dvd_refl

        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)
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

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)
See it in the graphDiscuss this resultChallenge it