AFTD Auto-Formalizing Theoretical Domains

odd_div_two_cancel_le

theoremverified

For odd n ≥ 3, if n * (n - 1) / 2 ≤ m * ((n - 1) / 2), then n ≤ m.

Statement

theorem odd_div_two_cancel_le (n m : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) (h : n * (n - 1) / 2 ≤ m * ((n - 1) / 2)) : n ≤ m
Source
step towards complete_graph_odd_line_graph_le_chromaticNumber
Verified
29 Oct 2026
Axioms
Quot.soundpropext

The proof, explained

Because n is odd, 2 divides n - 1, which lets us rewrite n * (n - 1) / 2 as n * ((n - 1) / 2). Since n ≥ 3, the factor (n - 1) / 2 is strictly positive, so cancelling it from both sides of the inequality yields n ≤ m.

  1. 2 divides n - 1

    Since n is odd (n % 2 = 1), n - 1 is even, witnessed explicitly by the quotient n / 2 via linear integer arithmetic (`omega`).

    line 3

      have hdvd : 2 ∣ (n - 1) := ⟨n / 2, by omega⟩
  2. The hypothesis h rewrites to n * ((n - 1) / 2) ≤ m * ((n - 1) / 2)

    Because 2 divides n - 1, Nat.mul_div_assoc allows moving the division by 2 inside the product: n * (n - 1) / 2 = n * ((n - 1) / 2).

    line 4

    uses Nat.mul_div_assoc

      rw [Nat.mul_div_assoc _ hdvd] at h
  3. (n - 1) / 2 > 0

    Since n ≥ 3, we have n - 1 ≥ 2, so (n - 1) / 2 ≥ 1 > 0, established by linear integer arithmetic (`omega`).

    line 5

      have hpos : 0 < (n - 1) / 2 := by omega
  4. n ≤ m

    Cancelling the strictly positive common factor (n - 1) / 2 from the right of both sides of the inequality h via Nat.le_of_mul_le_mul_right yields n ≤ m.

    line 6

    uses Nat.le_of_mul_le_mul_right

      exact Nat.le_of_mul_le_mul_right h hpos
Nat.mul_div_assoc
For natural numbers m, n, and k, if k divides n, then (m * n) / k = m * (n / k).
Nat.le_of_mul_le_mul_right
For natural numbers a, b, and c, if a * c ≤ b * c and c > 0, then a ≤ b.

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

/-- For odd n ≥ 3, cancellation of (n - 1) / 2 preserves inequality. -/theorem odd_div_two_cancel_le (n m : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) (h : n * (n - 1) / 2 ≤ m * ((n - 1) / 2)) : n ≤ m := by  have hdvd : 2 ∣ (n - 1) := ⟨n / 2, by omega⟩  rw [Nat.mul_div_assoc _ hdvd] at h  have hpos : 0 < (n - 1) / 2 := by omega  exact Nat.le_of_mul_le_mul_right h hpos
See it in the graphDiscuss this resultChallenge it