mondrian_sub_div_mul
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.
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).
obtain ⟨d, hd⟩ := hd have hy : y = x + a * d := by omega
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.
uses
Nat.add_mul_div_leftrw [hy, Nat.add_mul_div_left _ _ ha]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.
simp
Nat.add_mul_div_left- For natural numbers x, y, and z with y > 0, (x + y * z) / y = x / y + z.
- The operations are on natural numbers, where division truncates towards zero and subtraction is truncated at zero; the steps are valid because x ≤ y and a divides y - x.
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.
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