AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_free_factor_pair_encoding

theoremverified

In a positive factor pair of q^s times p^t whose first side is indivisible by q, that side is a pure p-power and the other side contains q^s.

Statement

theorem mondrian_prime_free_factor_pair_encoding (p q t s x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)
    (hpq : p ≠ q) (hx : 0 < x) (hy : 0 < y)
    (hxy : x * y = q ^ s * p ^ t) (hfree : ¬ q ∣ x) :
    x = p ^ x.factorization p ∧ y = q ^ s * p ^ y.factorization p ∧
      x.factorization p + y.factorization p = t
Source
Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The theorem characterizes factor pairs $x \cdot y = q^s p^t$ when $q \nmid x$. First, the general two-prime factorization gives $x = q^b p^{v_p(x)}$ and $y = q^c p^{v_p(y)}$ with $b + c = s$ and $v_p(x) + v_p(y) = t$. Since $q$ does not divide $x$, the exponent $b$ must be $0$, which forces $c = s$. Substituting these exponents into the decomposition shows that $x$ is a pure power of $p$ and $y$ contains the entire $q^s$ factor.

  1. There exist exponents $b, c \in \mathbb{N}$ such that $b + c = s$, $x = q^b p^{v_p(x)}$, $y = q^c p^{v_p(y)}$, and $v_p(x) + v_p(y) = t$.

    Apply `mondrian_two_prime_factor_pair_encoding` to the product $x y = q^s p^t$, decomposing $x$ and $y$ into their prime factors $p$ and $q$.

    line 6

    uses mondrian_two_prime_factor_pair_encoding

      obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t s x y hp hq hpq hx hy hxy
  2. The exponent $b$ of $q$ in $x$ must be $0$.

    Assume for contradiction that $b \neq 0$. By `dvd_pow_self`, $q \mid q^b$, which implies $q \mid q^b p^{v_p(x)} = x$ by `dvd_mul_of_dvd_left`. This contradicts the hypothesis `hfree` that $q \nmid x$.

    lines 7–11

    uses dvd_pow_self, dvd_mul_of_dvd_left

      have hb : b = 0 := by
        by_contra hh
        apply hfree
        rw [hxb]
        exact dvd_mul_of_dvd_left (dvd_pow_self q hh) _
  3. The exponent $c$ of $q$ in $y$ equals $s$.

    Since $b + c = s$ and $b = 0$, linear integer arithmetic (`omega`) determines that $c = s$.

    line 12

      have hc : c = s := by omega
  4. $x = p^{v_p(x)}$, $y = q^s p^{v_p(y)}$, and $v_p(x) + v_p(y) = t$.

    Substitute $b = 0$ and $c = s$ into the expressions for $x$ and $y$, simplifying $q^0$ to $1$ and $q^c$ to $q^s$, while retaining the sum of the $p$-exponents.

    line 13

    uses And.intro

      simpa [hb, hc] using And.intro hxb (And.intro hyc hv)
mondrian_two_prime_factor_pair_encoding
A positive factor pair $x y = q^s p^t$ for distinct primes $p$ and $q$ factors as $x = q^b p^{v_p(x)}$ and $y = q^c p^{v_p(y)}$ with $b + c = s$ and $v_p(x) + v_p(y) = t$.
dvd_pow_self
An element divides any of its positive powers: if $n \neq 0$, then $a \mid a^n$.
dvd_mul_of_dvd_left
If $a$ divides $b$, then $a$ divides $b c$ for any $c$.
And.intro
Given proofs of propositions $A$ and $B$, constructs a proof of the conjunction $A \land 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_free_factor_pair_encoding (p q t s x y : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)    (hpq : p ≠ q) (hx : 0 < x) (hy : 0 < y)    (hxy : x * y = q ^ s * p ^ t) (hfree : ¬ q ∣ x) :    x = p ^ x.factorization p ∧ y = q ^ s * p ^ y.factorization p ∧      x.factorization p + y.factorization p = t := by  obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t s x y hp hq hpq hx hy hxy  have hb : b = 0 := by    by_contra hh    apply hfree    rw [hxb]    exact dvd_mul_of_dvd_left (dvd_pow_self q hh) _  have hc : c = s := by omega  simpa [hb, hc] using And.intro hxb (And.intro hyc hv)
See it in the graphDiscuss this resultChallenge it