AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_free_height_two_chain_encoding

theoremverified

If x*y=q^s*r*p^a for primes p,q,r with p≠r, and q does not divide x, then y lies in one of the chains q^s*p^b or q^s*r*p^b.

Statement

theorem mondrian_prime_free_height_two_chain_encoding (p q r a s x y : ℕ)
    (hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpr : p ≠ r)
    (hxy : x * y = q ^ s * r * p ^ a) (hx : ¬ q ∣ x) :
    ∃ b : ℕ, y = q ^ s * p ^ b ∨ y = q ^ s * r * p ^ b
Source
For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

Since q is prime and does not divide x, q^s is coprime to x, so divisibility of x * y = q^s * r * p^a by q^s implies that q^s divides y, allowing us to write y = q^s * z. Canceling q^s yields x * z = r * p^a, which implies that z divides r^1 * p^a. Applying the two-prime divisor encoding theorem to z gives z = r^b * p^c with b ≤ 1, and the two possible values b = 0 and b = 1 place y in the chains q^s * p^c and q^s * r * p^c, respectively.

  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 q^s and x are coprime. Since q^s divides the product x * y = q^s * r * p^a (using dvd_mul_right and dvd_mul_of_dvd_left), coprimality implies that q^s divides y. We let z be the quotient satisfying y = q^s * z.

    lines 5–9

    uses dvd_mul_of_dvd_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_of_dvd_left (dvd_mul_right _ _) _)
      obtain ⟨z, hz⟩ := hy
  2. x * z = r * p^a.

    Substituting y = q^s * z into x * y = q^s * r * p^a gives x * (q^s * z) = q^s * (r * p^a), which rearranges to q^s * (x * z) = q^s * (r * p^a). Because q is prime, q > 0 and thus q^s > 0 by pow_pos. Canceling q^s from both sides using Nat.eq_of_mul_eq_mul_left yields x * z = r * p^a.

    lines 10–13

    uses Nat.eq_of_mul_eq_mul_left, pow_pos

      have hprod : x * z = r * p ^ a := by
        rw [hz] at hxy
        apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s)
        nlinarith [hxy]
  3. z divides r^1 * p^a.

    Rewriting r^1 as r using pow_one, the equality x * z = r * p^a shows that x witnesses that z divides r^1 * p^a.

    lines 14–16

    uses pow_one

      have hzdiv : z ∣ r ^ 1 * p ^ a := by
        rw [pow_one]
        exact ⟨x, by nlinarith [hprod]⟩
  4. z has the form r^b * p^(z.factorization p) with b ≤ 1, and choosing z.factorization p as the witness reduces the goal to showing y = q^s * p^(z.factorization p) ∨ y = q^s * r * p^(z.factorization p).

    Applying mondrian_two_prime_divisor_encoding to the distinct primes p and r and the divisor relation z ∣ r^1 * p^a yields an exponent b ≤ 1 such that z = r^b * p^(z.factorization p). We supply z.factorization p as the witness for the existential quantifier in the goal.

    lines 17–18

    uses mondrian_two_prime_divisor_encoding

      obtain ⟨b, hb, hzb⟩ := mondrian_two_prime_divisor_encoding p r a 1 z hp hr hpr hzdiv
      refine ⟨z.factorization p, ?_⟩
  5. The exponent b is either 0 or 1, splitting the proof into two cases.

    Since b is a natural number with b ≤ 1, linear arithmetic (via omega) determines that b = 0 or b = 1. We perform a case analysis on these two alternatives.

    lines 19–20

      have hbcase : b = 0 ∨ b = 1 := by omega
      rcases hbcase with rfl | rfl
  6. In the case b = 0, y = q^s * p^(z.factorization p), satisfying the left disjunct.

    When b = 0, the identity z = r^0 * p^(z.factorization p) simplifies to z = p^(z.factorization p) because r^0 = 1 (pow_zero) and 1 * p^k = p^k (one_mul). Multiplying both sides by q^s via congrArg and using y = q^s * z gives y = q^s * p^(z.factorization p).

    lines 21–22

    uses pow_zero, one_mul, congrArg

      · left
        simpa only [pow_zero, one_mul] using hz.trans (congrArg (fun v => q ^ s * v) hzb)
  7. In the case b = 1, y = q^s * r * p^(z.factorization p), satisfying the right disjunct.

    When b = 1, the identity z = r^1 * p^(z.factorization p) simplifies to z = r * p^(z.factorization p) because r^1 = r (pow_one). Multiplying both sides by q^s via congrArg, substituting y = q^s * z, and using the associativity of multiplication (Nat.mul_assoc) gives y = q^s * r * p^(z.factorization p).

    lines 23–24

    uses pow_one, Nat.mul_assoc, congrArg

      · right
        simpa only [pow_one, Nat.mul_assoc] using hz.trans (congrArg (fun v => q ^ s * v) hzb)
dvd_mul_of_dvd_left
If a divides b, then a divides b * c for any c.
dvd_mul_right
Any element a divides the product a * b.
Nat.eq_of_mul_eq_mul_left
For natural numbers, if n > 0 and n * m = n * k, then m = k.
pow_pos
Any power of a strictly positive element is strictly positive.
pow_one
Any element raised to the power 1 equals itself (a^1 = a).
mondrian_two_prime_divisor_encoding
For distinct primes p and q, every divisor x of q^s * p^t can be written as q^b * p^(x.factorization p) for some b ≤ s.
pow_zero
Any element raised to the power 0 equals 1 (a^0 = 1).
one_mul
Multiplying an element on the left by 1 leaves it unchanged (1 * a = a).
congrArg
If two inputs are equal, then applying any function to them yields equal outputs.
Nat.mul_assoc
Multiplication of natural numbers is associative: (n * m) * k = n * (m * k).

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_two_chain_encoding (p q r a s x y : ℕ)    (hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpr : p ≠ r)    (hxy : x * y = q ^ s * r * p ^ a) (hx : ¬ q ∣ x) :    ∃ b : ℕ, y = q ^ s * p ^ b ∨ y = q ^ s * r * p ^ b := 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_of_dvd_left (dvd_mul_right _ _) _)  obtain ⟨z, hz⟩ := hy  have hprod : x * z = r * p ^ a := by    rw [hz] at hxy    apply Nat.eq_of_mul_eq_mul_left (pow_pos hq.pos s)    nlinarith [hxy]  have hzdiv : z ∣ r ^ 1 * p ^ a := by    rw [pow_one]    exact ⟨x, by nlinarith [hprod]⟩  obtain ⟨b, hb, hzb⟩ := mondrian_two_prime_divisor_encoding p r a 1 z hp hr hpr hzdiv  refine ⟨z.factorization p, ?_⟩  have hbcase : b = 0 ∨ b = 1 := by omega  rcases hbcase with rfl | rfl  · left    simpa only [pow_zero, one_mul] using hz.trans (congrArg (fun v => q ^ s * v) hzb)  · right    simpa only [pow_one, Nat.mul_assoc] using hz.trans (congrArg (fun v => q ^ s * v) hzb)
See it in the graphDiscuss this resultChallenge it