AFTD Auto-Formalizing Theoretical Domains

nat_even_not_isPowerOfTwo_eq_two_pow_mul_odd

theoremverified

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.

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

    lines 4–6

    uses Nat.exists_eq_two_pow_mul_odd

      have hn0 : n ≠ 0 := by omega
      obtain ⟨a, m, hodd, rfl⟩ := Nat.exists_eq_two_pow_mul_odd hn0
      refine ⟨a, m, ?_, ?_, hodd, rfl⟩
  2. 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).

    lines 7–13

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

    lines 14–19

      · 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

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