AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_free_height_encoding

theoremverified

If x*y=q^s*p^t for primes p and q and q does not divide x, then y is q^s times a power of p; the primes need not be distinct.

Statement

theorem mondrian_prime_free_height_encoding (p q s t x y : ℕ) (hp : Nat.Prime p)
    (hq : Nat.Prime q) (hxy : x * y = q ^ s * p ^ t) (hx : ¬ q ∣ x) :
    ∃ a, y = q ^ s * p ^ a
Source
For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1
  • mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.

The proof, explained

Since q is prime and does not divide x, the power q^s is coprime to x. Because q^s divides x * y = q^s * p^t, Euclid's lemma forces q^s to divide y, allowing us to write y = q^s * z. Substituting this into the product equation and cancelling the non-zero factor q^s leaves x * z = p^t, so z divides p^t. Any divisor of a power of the prime p must itself be a power of p, which shows that y is q^s times a power of p.

  1. q^s divides y, so y = q^s * z for some natural number z.

    Since q is prime and does not divide x, q and x are coprime, which implies that q^s is coprime to x (by `pow_left`). From the equation x * y = q^s * p^t, q^s divides x * y (by `dvd_mul_right`). Because q^s is coprime to x, Gauss's lemma implies that q^s divides y. We unpack this divisibility to obtain an integer quotient z such that y = q^s * z.

    lines 4–6

    uses pow_left, dvd_mul_right

      have hcop : (q ^ s).Coprime x := (hq.coprime_iff_not_dvd.mpr hx).pow_left s
      have hy : q ^ s ∣ y := hcop.dvd_mul_left.mp (by rw [hxy]; exact dvd_mul_right _ _)
      obtain ⟨z, hz⟩ := hy
  2. x * z = p^t.

    Substituting y = q^s * z into x * y = q^s * p^t gives x * (q^s * z) = q^s * p^t, which can be rearranged to q^s * (x * z) = q^s * p^t. Since q is prime, q is strictly positive, hence q^s > 0 by `pow_pos`. Cancelling the common factor q^s from both sides using `Nat.eq_of_mul_eq_mul_left` yields x * z = p^t.

    lines 7–10

    uses pow_pos, Nat.eq_of_mul_eq_mul_left

      have hprod : x * z = p ^ t := by
        rw [hz] at hxy
        apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s)
        nlinarith [hxy]
  3. z is a power of p, specifically z = p ^ (z.factorization p).

    The relation x * z = p^t shows that z divides p^t. Since p is prime, any divisor of a power of p is itself a power of p. Applying `mondrian_dvd_prime_pow_eq` gives z = p ^ (z.factorization p), where z.factorization p is the multiplicity of p in z.

    line 11

    uses mondrian_dvd_prime_pow_eq

      have hzpow := mondrian_dvd_prime_pow_eq p t z hp ⟨x, by nlinarith [hprod]⟩
  4. There exists an exponent a such that y = q^s * p^a.

    We provide a = z.factorization p as the witness. Since y = q^s * z, multiplying both sides of z = p ^ (z.factorization p) by q^s using `congrArg` gives y = q^s * p ^ (z.factorization p).

    lines 12–14

    uses congrArg

      refine ⟨z.factorization p, ?_⟩
      rw [hz]
      exact congrArg (fun v => q ^ s * v) hzpow
pow_left
If m is coprime to k, then any power m^n is also coprime to k.
dvd_mul_right
An element a divides the product a * b.
Nat.eq_of_mul_eq_mul_left
If n > 0 and n * m = n * k for natural numbers, then m = k.
pow_pos
A strictly positive element raised to any power is strictly positive.
mondrian_dvd_prime_pow_eq
If p is prime and x divides p^e, then x is p raised to the multiplicity of p in x.
congrArg
If two inputs are equal, then applying the same function to them yields equal outputs.

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_free_height_encoding (p q s t x y : ℕ) (hp : Nat.Prime p)    (hq : Nat.Prime q) (hxy : x * y = q ^ s * p ^ t) (hx : ¬ q ∣ x) :    ∃ a, y = q ^ s * p ^ a := by  have hcop : (q ^ s).Coprime x := (hq.coprime_iff_not_dvd.mpr hx).pow_left s  have hy : q ^ s ∣ y := hcop.dvd_mul_left.mp (by rw [hxy]; exact dvd_mul_right _ _)  obtain ⟨z, hz⟩ := hy  have hprod : x * z = p ^ t := by    rw [hz] at hxy    apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s)    nlinarith [hxy]  have hzpow := mondrian_dvd_prime_pow_eq p t z hp ⟨x, by nlinarith [hprod]⟩  refine ⟨z.factorization p, ?_⟩  rw [hz]  exact congrArg (fun v => q ^ s * v) hzpow
See it in the graphDiscuss this resultChallenge it