prime_ge_two_mul_add_one_of_odd_k
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.
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.
have hdiv' := hdiv obtain ⟨m, hm⟩ := hdiv
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.
uses
Nat.le_of_dvdhave 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
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.
uses
Nat.Odd.sub_odd,odd_onehave hl_odd : Odd l := hl.odd_of_ne_two hl2 have hEven : Even (l - 1) := Nat.Odd.sub_odd hl_odd odd_one
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.
uses
Nat.even_mul.mp,Nat.not_even_iff_odd.mprhave 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
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.
uses
Nat.mul_zerohave 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
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.
uses
Nat.one_lt_of_ne_zero_of_evenhave hm_ge : 2 ≤ m := by have h1 := Nat.one_lt_of_ne_zero_of_even hm_ne0 hm_even omega
l = k * m + 1.
Since l is prime, l > 1. Rearranging l - 1 = k * m via linear arithmetic over ℕ yields l = k * m + 1.
have hl_eq : l = k * m + 1 := by have hl1 := hl.one_lt omega
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.
uses
Nat.mul_le_mul_lefthave hkm : 2 * k ≤ k * m := by calc 2 * k = k * 2 := by ring _ ≤ k * m := Nat.mul_le_mul_left k hm_ge
2 * k + 1 ≤ l.
Combining l = k * m + 1 with 2 * k ≤ k * m immediately implies 2 * k + 1 ≤ l by linear arithmetic over ℕ.
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
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.
/-- 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