AFTD Auto-Formalizing Theoretical Domains

prime_ge_two_mul_add_one_of_odd_k

theoremverified

If l is a prime number and k ≥ 2 is an odd natural number such that k divides l - 1, then l ≥ 2 * k + 1.

Statement

theorem prime_ge_two_mul_add_one_of_odd_k {l k : ℕ} (hl : Nat.Prime l) (hk_odd : Odd k)
    (hdiv : k ∣ l - 1) (hk_ge : 2 ≤ k) :
    2 * k + 1 ≤ l
Source
arXiv:2610.28047 Corollary 3.2
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any natural numbers $l$ and $k$, if $l$ is prime, $k$ is odd, $k$ divides $l - 1$, and $2 \le k$, then $2k + 1 \le l$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

We write l - 1 = k * m for some natural number m. Since l is a prime and cannot equal 2 (as that would force k ≤ 1), l is odd, which makes l - 1 even. Because k is odd, the factor m must be even and non-zero, which forces m ≥ 2. Consequently, l = k * m + 1 ≥ 2 * k + 1.

  1. There exists a natural number m such that l - 1 = k * m.

    We save a copy of the divisibility assumption k ∣ l - 1 and unpack it into a natural number m such that l - 1 = k * m.

    lines 5–6

      have hdiv' := hdiv
      obtain ⟨m, hm⟩ := hdiv
  2. l ≠ 2.

    Suppose, for contradiction, that l = 2. Then k divides 2 - 1 = 1. Since 1 > 0, Nat.le_of_dvd implies k ≤ 1, which contradicts the hypothesis that 2 ≤ k.

    lines 7–12

    uses Nat.le_of_dvd

      have hl2 : l ≠ 2 := by
        intro h
        subst l
        have h1 : k ∣ 1 := by simpa using hdiv'
        have hk1 : k ≤ 1 := Nat.le_of_dvd (by norm_num) h1
        omega
  3. l - 1 is even.

    Because l is prime and l ≠ 2, l is odd. Since 1 is odd by odd_one, the difference l - 1 of two odd numbers is even by Nat.Odd.sub_odd.

    lines 13–14

    uses Nat.Odd.sub_odd, odd_one

      have hl_odd : Odd l := hl.odd_of_ne_two hl2
      have hEven : Even (l - 1) := Nat.Odd.sub_odd hl_odd odd_one
  4. m is even.

    Substituting l - 1 = k * m shows that k * m is even. By Nat.even_mul.mp, either k is even or m is even. Since k is odd, Nat.not_even_iff_odd.mpr rules out k being even, leaving m even.

    lines 15–19

    uses Nat.even_mul.mp, Nat.not_even_iff_odd.mpr

      have hm_even : Even m := by
        rw [hm] at hEven
        rcases Nat.even_mul.mp hEven with hk_even | hm_even
        · exact absurd hk_even (Nat.not_even_iff_odd.mpr hk_odd)
        · exact hm_even
  5. m ≠ 0.

    Suppose m = 0. Then l - 1 = k * 0 = 0 by Nat.mul_zero. Because any prime satisfies l ≥ 2, l - 1 = 0 forces l = 1, contradicting the fact that primes cannot equal 1.

    lines 20–25

    uses Nat.mul_zero

      have hm_ne0 : m ≠ 0 := by
        intro hm0
        rw [hm0, Nat.mul_zero] at hm
        have hl2le := hl.two_le
        have hl1 : l = 1 := by omega
        exact hl.ne_one hl1
  6. 2 ≤ m.

    Because m is non-zero and even, Nat.one_lt_of_ne_zero_of_even yields 1 < m, which is equivalent to 2 ≤ m over the natural numbers.

    lines 26–28

    uses Nat.one_lt_of_ne_zero_of_even

      have hm_ge : 2 ≤ m := by
        have h1 := Nat.one_lt_of_ne_zero_of_even hm_ne0 hm_even
        omega
  7. l = k * m + 1.

    Since l is prime, l > 1. Rearranging l - 1 = k * m via linear arithmetic over ℕ yields l = k * m + 1.

    lines 29–31

      have hl_eq : l = k * m + 1 := by
        have hl1 := hl.one_lt
        omega
  8. 2 * k ≤ k * m.

    We have 2 * k = k * 2 by ring arithmetic. Since 2 ≤ m, multiplying on the left by k preserves the inequality by Nat.mul_le_mul_left, giving k * 2 ≤ k * m.

    lines 32–34

    uses Nat.mul_le_mul_left

      have hkm : 2 * k ≤ k * m := by
        calc 2 * k = k * 2 := by ring
          _ ≤ k * m := Nat.mul_le_mul_left k hm_ge
  9. 2 * k + 1 ≤ l.

    Combining l = k * m + 1 with 2 * k ≤ k * m immediately implies 2 * k + 1 ≤ l by linear arithmetic over ℕ.

    line 35

      omega
Nat.le_of_dvd
If a natural number m divides a positive natural number n, then m ≤ n.
Nat.Odd.sub_odd
The difference of two odd natural numbers is even.
odd_one
The number 1 is odd.
Nat.even_mul.mp
If the product of two natural numbers is even, then at least one factor is even.
Nat.not_even_iff_odd.mpr
An odd natural number is not even.
Nat.mul_zero
Multiplying any natural number by zero gives zero.
Nat.one_lt_of_ne_zero_of_even
A non-zero even natural number is strictly greater than 1.
Nat.mul_le_mul_left
Multiplying both sides of an inequality by a natural number on the left preserves the inequality.

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

/-- An odd divisor k ≥ 2 of l - 1 for a prime l satisfies l ≥ 2k + 1. -/theorem prime_ge_two_mul_add_one_of_odd_k {l k : ℕ} (hl : Nat.Prime l) (hk_odd : Odd k)    (hdiv : k ∣ l - 1) (hk_ge : 2 ≤ k) :    2 * k + 1 ≤ l := by  have hdiv' := hdiv  obtain ⟨m, hm⟩ := hdiv  have hl2 : l ≠ 2 := by    intro h    subst l    have h1 : k ∣ 1 := by simpa using hdiv'    have hk1 : k ≤ 1 := Nat.le_of_dvd (by norm_num) h1    omega  have hl_odd : Odd l := hl.odd_of_ne_two hl2  have hEven : Even (l - 1) := Nat.Odd.sub_odd hl_odd odd_one  have hm_even : Even m := by    rw [hm] at hEven    rcases Nat.even_mul.mp hEven with hk_even | hm_even    · exact absurd hk_even (Nat.not_even_iff_odd.mpr hk_odd)    · exact hm_even  have hm_ne0 : m ≠ 0 := by    intro hm0    rw [hm0, Nat.mul_zero] at hm    have hl2le := hl.two_le    have hl1 : l = 1 := by omega    exact hl.ne_one hl1  have hm_ge : 2 ≤ m := by    have h1 := Nat.one_lt_of_ne_zero_of_even hm_ne0 hm_even    omega  have hl_eq : l = k * m + 1 := by    have hl1 := hl.one_lt    omega  have hkm : 2 * k ≤ k * m := by    calc 2 * k = k * 2 := by ring      _ ≤ k * m := Nat.mul_le_mul_left k hm_ge  omega
See it in the graphDiscuss this resultChallenge it