AFTD Auto-Formalizing Theoretical Domains

mondrian_sub_div_mul

theoremverified

For x at most y and positive a dividing y minus x, the quotient-coordinate difference multiplied by a is y minus x.

Statement

theorem mondrian_sub_div_mul (a x y : ℕ) (ha : 0 < a) (hxy : x ≤ y)
    (hd : a ∣ y - x) : a * (y / a - x / a) = y - x
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • mondrian_rect_div_dimensionsDividing coordinates of a positive rectangle whose side lengths are multiples of a divides its width and height exactly by a.

The proof, explained

Since a divides y - x with x ≤ y, we can write y = x + a * d for some natural number d. Substituting this expression for y allows distributing the division in (x + a * d) / a as x / a + d. The terms x / a on the left and x on the right cancel, reducing both sides to a * d.

  1. We can express y as x + a * d for some natural number d.

    Since a divides y - x, there is a natural number d such that y - x = a * d. Because x ≤ y, adding x to both sides yields y = x + a * d, verified by linear arithmetic (omega).

    lines 3–4

      obtain ⟨d, hd⟩ := hd
      have hy : y = x + a * d := by omega
  2. The goal reduces to a * (x / a + d - x / a) = x + a * d - x.

    Substitute y = x + a * d into both sides. Since a > 0, the library lemma Nat.add_mul_div_left rewrites the division (x + a * d) / a as x / a + d.

    line 5

    uses Nat.add_mul_div_left

      rw [hy, Nat.add_mul_div_left _ _ ha]
  3. Both sides evaluate to a * d, completing the proof.

    On the left-hand side, x / a cancels from (x / a + d) - x / a, leaving a * d. On the right-hand side, x cancels from (x + a * d) - x, also leaving a * d. The simplifier performs these cancellations and closes the goal.

    line 6

      simp
Nat.add_mul_div_left
For natural numbers x, y, and z with y > 0, (x + y * z) / y = x / y + z.

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

theorem mondrian_sub_div_mul (a x y : ℕ) (ha : 0 < a) (hxy : x ≤ y)    (hd : a ∣ y - x) : a * (y / a - x / a) = y - x := by  obtain ⟨d, hd⟩ := hd  have hy : y = x + a * d := by omega  rw [hy, Nat.add_mul_div_left _ _ ha]  simp
See it in the graphDiscuss this resultChallenge it