mondrian_prime_power_dvd_sides
If p is prime and exceeds c, positive x and y at most c times p to the e whose product is divisible by p to the 2e must each be divisible by p to the e.
Statement
theorem mondrian_prime_power_dvd_sides (c p e x y : ℕ) (hp : Nat.Prime p)
(hpc : c < p) (hx : 0 < x) (hy : 0 < y)
(hxn : x ≤ c * p ^ e) (hyn : y ≤ c * p ^ e)
(hxy : p ^ (2 * e) ∣ x * y) : p ^ e ∣ x ∧ p ^ e ∣ y- 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_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
The proof, explained
Because p^(2e) divides xy, it factors as a * b with a dividing x and b dividing y; since p is prime, these factors must be prime powers p^i and p^j whose exponents sum to 2e. The upper bounds x, y ≤ c * p^e with c < p force both p^i ≤ x < p^(e + 1) and p^j ≤ y < p^(e + 1), which means i ≤ e and j ≤ e. Because their sum is 2e, both exponents must equal e, showing that p^e divides x and p^e divides y.
There exist natural numbers a and b such that a divides x, b divides y, and p^(2e) = a * b.
Since p^(2e) divides the product x * y, the general decomposition property of divisibility in the natural numbers (`exists_dvd_and_dvd_of_dvd_mul`) splits p^(2e) into factors a and b dividing x and y respectively.
uses
exists_dvd_and_dvd_of_dvd_mulobtain ⟨a, b, hax, hby, hab⟩ := exists_dvd_and_dvd_of_dvd_mul hxyThe factors a and b are prime powers: a = p^i and b = p^j for some exponents i, j ≤ 2e.
Because p^(2e) = a * b, a and b each divide p^(2e) via `dvd_mul_right` and `dvd_mul_left`. By `Nat.dvd_prime_pow`, every divisor of a power of a prime p is itself a power of p, giving a = p^i and b = p^j with i, j ≤ 2e. Lean substitutes these representations directly for a and b.
uses
dvd_mul_right,dvd_mul_left,Nat.dvd_prime_powhave ha : a ∣ p ^ (2 * e) := by rw [hab]; exact dvd_mul_right a b have hb : b ∣ p ^ (2 * e) := by rw [hab]; exact dvd_mul_left b a obtain ⟨i, hi, rfl⟩ := (Nat.dvd_prime_pow hp).mp ha obtain ⟨j, hj, rfl⟩ := (Nat.dvd_prime_pow hp).mp hb
The exponents satisfy 2e = i + j.
The factorization identity becomes p^(2e) = p^i * p^j = p^(i + j) using `pow_add`. Because p is prime, p ≥ 2, so the base-p exponentiation is injective (`Nat.pow_right_injective`), which equates the exponents 2e = i + j.
uses
Nat.pow_right_injective,pow_addhave hij : 2 * e = i + j := by apply Nat.pow_right_injective hp.two_le simpa only [pow_add] using hab
The prime power p^i satisfies p^i < p^(e + 1).
Because p^i divides the positive integer x, we have p^i ≤ x by `Nat.le_of_dvd`. Using the hypothesis x ≤ c * p^e, the assumption c < p, and positivity of p^e (`pow_pos`), strict monotonicity of multiplication (`Nat.mul_lt_mul_of_pos_right`) gives c * p^e < p * p^e. Since p * p^e = p^(e + 1) by commutativity and `pow_succ`, chaining the inequalities yields p^i < p^(e + 1).
uses
Nat.le_of_dvd,Nat.mul_lt_mul_of_pos_right,pow_pos,pow_succ,Nat.mul_commhave hxe : p ^ i < p ^ (e + 1) := by calc p ^ i ≤ x := Nat.le_of_dvd hx hax _ ≤ c * p ^ e := hxn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm]
The prime power p^j satisfies p^j < p^(e + 1).
Symmetrically, p^j ≤ y by `Nat.le_of_dvd`. Chaining with y ≤ c * p^e < p * p^e = p^(e + 1) using `Nat.mul_lt_mul_of_pos_right`, `pow_pos`, `pow_succ`, and `Nat.mul_comm` gives p^j < p^(e + 1).
uses
Nat.le_of_dvd,Nat.mul_lt_mul_of_pos_right,pow_pos,pow_succ,Nat.mul_commhave hye : p ^ j < p ^ (e + 1) := by calc p ^ j ≤ y := Nat.le_of_dvd hy hby _ ≤ c * p ^ e := hyn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm]
The exponents i and j both equal e.
Since base p > 1, exponentiation is strictly order-preserving (`Nat.pow_lt_pow_iff_right`). Thus p^i < p^(e + 1) implies i < e + 1 (so i ≤ e), and p^j < p^(e + 1) implies j < e + 1 (so j ≤ e). Together with i + j = 2e, the two inequalities force i = e and j = e, verified by linear integer arithmetic (`omega`).
uses
Nat.pow_lt_pow_iff_righthave hi' := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hxe have hj' := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hye have hie : i = e := by omega have hje : j = e := by omega
p^e divides x and p^e divides y.
We already know p^i divides x and p^j divides y. Combining these two facts with `And.intro` and replacing i and j with e completes the proof.
uses
And.introsimpa [hie, hje] using And.intro hax hby
exists_dvd_and_dvd_of_dvd_mul- In a decomposition monoid (such as the natural numbers), if a divides b * c, then a decomposes into a product a₁ * a₂ such that a₁ divides b and a₂ divides c.
dvd_mul_right- An element a always divides a * b.
dvd_mul_left- An element a always divides b * a in a commutative semigroup.
Nat.dvd_prime_pow- A positive integer divides a prime power p^m if and only if it is itself p^k for some k ≤ m.
Nat.pow_right_injective- For any integer base a ≥ 2, the exponential function x ↦ a^x is injective.
pow_add- Exponentiation converts addition in the exponent to multiplication: a^(m + n) = a^m * a^n.
Nat.le_of_dvd- If m divides a strictly positive natural number n, then m ≤ n.
Nat.mul_lt_mul_of_pos_right- Multiplying both sides of a strict inequality n < m by a positive integer preserves the strict inequality.
pow_pos- Any power of a strictly positive element is strictly positive.
pow_succ- The successor power satisfies a^(n + 1) = a^n * a.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.pow_lt_pow_iff_right- For a base a > 1, a^n < a^m holds if and only if n < m.
And.intro- Given a proof of A and a proof of B, construct a proof of A ∧ B.
- The equalities i = e and j = e in lines 27 and 28 are discharged by the `omega` decision procedure via linear integer arithmetic on the constraints i ≤ e, j ≤ e, and i + j = 2e.
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_prime_power_dvd_sides (c p e x y : ℕ) (hp : Nat.Prime p) (hpc : c < p) (hx : 0 < x) (hy : 0 < y) (hxn : x ≤ c * p ^ e) (hyn : y ≤ c * p ^ e) (hxy : p ^ (2 * e) ∣ x * y) : p ^ e ∣ x ∧ p ^ e ∣ y := by obtain ⟨a, b, hax, hby, hab⟩ := exists_dvd_and_dvd_of_dvd_mul hxy have ha : a ∣ p ^ (2 * e) := by rw [hab]; exact dvd_mul_right a b have hb : b ∣ p ^ (2 * e) := by rw [hab]; exact dvd_mul_left b a obtain ⟨i, hi, rfl⟩ := (Nat.dvd_prime_pow hp).mp ha obtain ⟨j, hj, rfl⟩ := (Nat.dvd_prime_pow hp).mp hb have hij : 2 * e = i + j := by apply Nat.pow_right_injective hp.two_le simpa only [pow_add] using hab have hxe : p ^ i < p ^ (e + 1) := by calc p ^ i ≤ x := Nat.le_of_dvd hx hax _ ≤ c * p ^ e := hxn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm] have hye : p ^ j < p ^ (e + 1) := by calc p ^ j ≤ y := Nat.le_of_dvd hy hby _ ≤ c * p ^ e := hyn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm] have hi' := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hxe have hj' := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hye have hie : i = e := by omega have hje : j = e := by omega simpa [hie, hje] using And.intro hax hby