AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_power_dvd_sides

theoremverified

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.

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

    line 5

    uses exists_dvd_and_dvd_of_dvd_mul

      obtain ⟨a, b, hax, hby, hab⟩ := exists_dvd_and_dvd_of_dvd_mul hxy
  2. The 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.

    lines 6–9

    uses dvd_mul_right, dvd_mul_left, Nat.dvd_prime_pow

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

    lines 10–12

    uses Nat.pow_right_injective, pow_add

      have hij : 2 * e = i + j := by
        apply Nat.pow_right_injective hp.two_le
        simpa only [pow_add] using hab
  4. 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).

    lines 13–18

    uses Nat.le_of_dvd, Nat.mul_lt_mul_of_pos_right, pow_pos, pow_succ, Nat.mul_comm

      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]
  5. 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).

    lines 19–24

    uses Nat.le_of_dvd, Nat.mul_lt_mul_of_pos_right, pow_pos, 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]
  6. 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`).

    lines 25–28

    uses Nat.pow_lt_pow_iff_right

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

    line 29

    uses And.intro

      simpa [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.

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