nat_even_not_isPowerOfTwo_eq_two_pow_mul_odd
Every even integer n ≥ 6 that is not a power of 2 factors uniquely as 2^a * m with a ≥ 1, m ≥ 3, and m odd.
Statement
theorem nat_even_not_isPowerOfTwo_eq_two_pow_mul_odd (n : ℕ) (hn : 6 ≤ n) (heven : Even n) (hpow : ¬ n.isPowerOfTwo) :
∃ (a : ℕ) (m : ℕ), 1 ≤ a ∧ 3 ≤ m ∧ Odd m ∧ n = 2 ^ a * m- Source
- step towards harborth_bound_equality_rank_three
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof extracts the canonical factorization n = 2^a * m with m odd from the fact that n is non-zero. If a were 0, then n = m would be odd, contradicting the assumption that n is even; hence a ≥ 1. If m < 3, then being odd forces m = 1, making n = 2^a a power of 2 and contradicting the hypothesis that n is not a power of 2; hence m ≥ 3.
Factor n as 2^a * m with m odd, reducing the theorem to showing 1 ≤ a and 3 ≤ m.
Because n ≥ 6, n is non-zero (via omega). Applying Nat.exists_eq_two_pow_mul_odd decomposes n into 2^a * m with m odd. Providing a and m as witnesses leaves two remaining goals: showing 1 ≤ a and 3 ≤ m.
uses
Nat.exists_eq_two_pow_mul_oddhave hn0 : n ≠ 0 := by omega obtain ⟨a, m, hodd, rfl⟩ := Nat.exists_eq_two_pow_mul_odd hn0 refine ⟨a, m, ?_, ?_, hodd, rfl⟩
The exponent a is at least 1.
Assume for contradiction that a < 1, which means a = 0. Substituting a = 0, the equality n = 2^0 * m simplifies via pow_zero and one_mul to n = m. Thus m must be even since n is even. But m is also odd, so m = 2k + 1 and m = 2j for some integers k and j, which is impossible by parity (closed by omega).
uses
pow_zero,one_mul· by_contra ha have ha0 : a = 0 := by omega subst ha0 simp only [pow_zero, one_mul] at heven rcases hodd with ⟨k, rfl⟩ rcases heven with ⟨j, hj⟩ omega
The odd factor m is at least 3.
Assume for contradiction that m < 3. Because m is odd (m = 2k + 1), the only odd natural number strictly less than 3 is m = 1 (deduced by omega). Substituting m = 1 gives n = 2^a * 1 = 2^a, which exhibits n as a power of 2 and directly contradicts the hypothesis hpow.
· by_contra hm have hm1 : m = 1 := by rcases hodd with ⟨k, rfl⟩ omega subst hm1 exact hpow ⟨a, by ring⟩
Nat.exists_eq_two_pow_mul_odd- Every non-zero natural number can be factored as 2^k * m for some natural k and odd natural m.
pow_zero- Any element raised to the power 0 equals 1.
one_mul- Multiplying an element on the left by 1 leaves it unchanged.
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.
/-- Every even integer n ≥ 6 that is not a power of 2 can be factored as 2^a * m with a ≥ 1, m ≥ 3, and m odd. -/theorem nat_even_not_isPowerOfTwo_eq_two_pow_mul_odd (n : ℕ) (hn : 6 ≤ n) (heven : Even n) (hpow : ¬ n.isPowerOfTwo) : ∃ (a : ℕ) (m : ℕ), 1 ≤ a ∧ 3 ≤ m ∧ Odd m ∧ n = 2 ^ a * m := by have hn0 : n ≠ 0 := by omega obtain ⟨a, m, hodd, rfl⟩ := Nat.exists_eq_two_pow_mul_odd hn0 refine ⟨a, m, ?_, ?_, hodd, rfl⟩ · by_contra ha have ha0 : a = 0 := by omega subst ha0 simp only [pow_zero, one_mul] at heven rcases hodd with ⟨k, rfl⟩ rcases heven with ⟨j, hj⟩ omega · by_contra hm have hm1 : m = 1 := by rcases hodd with ⟨k, rfl⟩ omega subst hm1 exact hpow ⟨a, by ring⟩