AFTD Auto-Formalizing Theoretical Domains

mondrian_two_prime_factor_pair_encoding

theoremverified

A positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.

Statement

theorem mondrian_two_prime_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) :
    ∃ b c, b + c = s ∧ x = q ^ b * p ^ (x.factorization p) ∧
      y = q ^ c * 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 3
Used by 4

The proof, explained

The theorem establishes that any positive factor pair x * y = q^s * p^t decomposes such that x = q^b * p^(v_p(x)) and y = q^c * p^(v_p(y)) with complementary exponents b + c = s and v_p(x) + v_p(y) = t. The proof first applies a divisor encoding lemma to express x and y in terms of powers of q and p. Because p and q are distinct primes, neither divides the other, so taking p-adic and q-adic valuations of both sides of x * y = q^s * p^t separates the prime powers and yields the required sums of exponents.

  1. Both x and y decompose into powers of q and p: x = q^b * p^(v_p(x)) and y = q^c * p^(v_p(y)) for some exponents b ≤ s and c ≤ s.

    Because x * y = q^s * p^t, both x and y divide q^s * p^t (witnessed by each other). Applying the divisor encoding lemma `mondrian_two_prime_divisor_encoding` to x and y produces exponents b ≤ s and c ≤ s such that x = q^b * p^(v_p(x)) and y = q^c * p^(v_p(y)).

    lines 5–6

    uses mondrian_two_prime_divisor_encoding

      obtain ⟨b, hb, hxb⟩ := mondrian_two_prime_divisor_encoding p q t s x hp hq hpq ⟨y, hxy.symm⟩
      obtain ⟨c, hc, hyc⟩ := mondrian_two_prime_divisor_encoding p q t s y hp hq hpq ⟨x, by nlinarith [hxy]⟩
  2. Neither prime divides the other: p ∤ q and q ∤ p.

    If p were to divide q, then by `Nat.dvd_prime` p must be either 1 or q. But p is prime (so p ≠ 1) and p ≠ q by assumption, a contradiction. By symmetry, the same argument shows q cannot divide p.

    lines 7–16

    uses Nat.dvd_prime

      have hnot : ¬ p ∣ q := by
        intro hh
        rcases (Nat.dvd_prime hq).mp hh with hh | hh
        · exact hp.ne_one hh
        · exact hpq hh
      have hnot' : ¬ q ∣ p := by
        intro hh
        rcases (Nat.dvd_prime hp).mp hh with hh | hh
        · exact hq.ne_one hh
        · exact hpq hh.symm
  3. The p-adic and q-adic valuations of x * y equal those of q^s * p^t.

    Applying the factorization projections at p and q to both sides of the hypothesis x * y = q^s * p^t using `congrArg` gives equality of the respective valuations.

    lines 17–18

    uses congrArg

      have hvp := congrArg (fun z : ℕ => z.factorization p) hxy
      have hvq := congrArg (fun z : ℕ => z.factorization q) hxy
  4. The p-adic valuations of x and y sum to t: v_p(x) + v_p(y) = t.

    Because x and y are positive, the p-adic valuation of their product is v_p(x) + v_p(y) by `Nat.factorization_mul`. On the right-hand side, the valuation of q^s * p^t is s * v_p(q) + t * v_p(p). Since p ∤ q, v_p(q) = 0 by `Nat.factorization_eq_zero_of_not_dvd`, and v_p(p) = 1, so the valuation simplifies to t. Equating both sides yields v_p(x) + v_p(y) = t.

    lines 19–23

    uses Nat.factorization_mul, pow_ne_zero, Nat.factorization_pow, Nat.factorization_eq_zero_of_not_dvd

      have hv : x.factorization p + y.factorization p = t := by
        simpa [Nat.factorization_mul (by omega : x ≠ 0) (by omega : y ≠ 0),
          Nat.factorization_mul (pow_ne_zero s hq.ne_zero) (pow_ne_zero t hp.ne_zero),
          Nat.factorization_pow, Nat.factorization_eq_zero_of_not_dvd hnot,
          hp.factorization_self] using hvp
  5. The q-adic valuations of x and y are b and c, respectively (v_q(x) = b and v_q(y) = c).

    Taking the q-adic valuation of x = q^b * p^(v_p(x)) gives v_q(x) = b * v_q(q) + v_p(x) * v_q(p) by multiplicativity (`Nat.factorization_mul`) and `Nat.factorization_pow`. Since v_q(q) = 1 and q ∤ p (so v_q(p) = 0 by `Nat.factorization_eq_zero_of_not_dvd`), this reduces to v_q(x) = b. Symmetrically, the same calculation for y = q^c * p^(v_p(y)) yields v_q(y) = c.

    lines 24–33

    uses Nat.factorization_mul, pow_ne_zero, Nat.factorization_pow, Nat.factorization_eq_zero_of_not_dvd

      have hxq : x.factorization q = b := by
        rw [hxb, Nat.factorization_mul (pow_ne_zero b hq.ne_zero)
          (pow_ne_zero (x.factorization p) hp.ne_zero)]
        simp [Nat.factorization_pow, hq.factorization_self,
          Nat.factorization_eq_zero_of_not_dvd hnot']
      have hyq : y.factorization q = c := by
        rw [hyc, Nat.factorization_mul (pow_ne_zero c hq.ne_zero)
          (pow_ne_zero (y.factorization p) hp.ne_zero)]
        simp [Nat.factorization_pow, hq.factorization_self,
          Nat.factorization_eq_zero_of_not_dvd hnot']
  6. The exponents b and c sum to s: b + c = s.

    Taking the q-adic valuation of x * y = q^s * p^t, the left-hand side is v_q(x) + v_q(y) = b + c, while the right-hand side evaluates to s * v_q(q) + t * v_q(p) = s * 1 + 0 = s. Hence b + c = s.

    lines 34–38

    uses Nat.factorization_mul, pow_ne_zero, Nat.factorization_pow, Nat.factorization_eq_zero_of_not_dvd

      have hbc : b + c = s := by
        simpa [Nat.factorization_mul (by omega : x ≠ 0) (by omega : y ≠ 0),
          Nat.factorization_mul (pow_ne_zero s hq.ne_zero) (pow_ne_zero t hp.ne_zero),
          Nat.factorization_pow, hq.factorization_self,
          Nat.factorization_eq_zero_of_not_dvd hnot', hxq, hyq] using hvq
  7. The exponents b and c satisfy all existential requirements of the theorem.

    We assemble the witnesses b and c together with the proofs of b + c = s, the encodings of x and y, and v_p(x) + v_p(y) = t to satisfy the existential goal.

    line 39

      exact ⟨b, c, hbc, hxb, hyc, hv⟩
mondrian_two_prime_divisor_encoding
If p and q are distinct primes, any divisor x of q^s * p^t factors as q^b * p^(v_p(x)) for some exponent b ≤ s.
Nat.dvd_prime
A natural number divides a prime p if and only if it is equal to 1 or p.
congrArg
If two expressions are equal, applying any function to both preserves equality (a = b implies f(a) = f(b)).
Nat.factorization_mul
The prime factorization of a product of nonzero natural numbers is the sum of their individual factorizations.
pow_ne_zero
Any natural power of a nonzero element is nonzero.
Nat.factorization_pow
The prime factorization of a power n^k is k times the prime factorization of n.
Nat.factorization_eq_zero_of_not_dvd
If a prime p does not divide n, then the exponent of p in the prime factorization of n is zero.

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_two_prime_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) :    ∃ b c, b + c = s ∧ x = q ^ b * p ^ (x.factorization p) ∧      y = q ^ c * p ^ (y.factorization p) ∧ x.factorization p + y.factorization p = t := by  obtain ⟨b, hb, hxb⟩ := mondrian_two_prime_divisor_encoding p q t s x hp hq hpq ⟨y, hxy.symm⟩  obtain ⟨c, hc, hyc⟩ := mondrian_two_prime_divisor_encoding p q t s y hp hq hpq ⟨x, by nlinarith [hxy]⟩  have hnot : ¬ p ∣ q := by    intro hh    rcases (Nat.dvd_prime hq).mp hh with hh | hh    · exact hp.ne_one hh    · exact hpq hh  have hnot' : ¬ q ∣ p := by    intro hh    rcases (Nat.dvd_prime hp).mp hh with hh | hh    · exact hq.ne_one hh    · exact hpq hh.symm  have hvp := congrArg (fun z : ℕ => z.factorization p) hxy  have hvq := congrArg (fun z : ℕ => z.factorization q) hxy  have hv : x.factorization p + y.factorization p = t := by    simpa [Nat.factorization_mul (by omega : x ≠ 0) (by omega : y ≠ 0),      Nat.factorization_mul (pow_ne_zero s hq.ne_zero) (pow_ne_zero t hp.ne_zero),      Nat.factorization_pow, Nat.factorization_eq_zero_of_not_dvd hnot,      hp.factorization_self] using hvp  have hxq : x.factorization q = b := by    rw [hxb, Nat.factorization_mul (pow_ne_zero b hq.ne_zero)      (pow_ne_zero (x.factorization p) hp.ne_zero)]    simp [Nat.factorization_pow, hq.factorization_self,      Nat.factorization_eq_zero_of_not_dvd hnot']  have hyq : y.factorization q = c := by    rw [hyc, Nat.factorization_mul (pow_ne_zero c hq.ne_zero)      (pow_ne_zero (y.factorization p) hp.ne_zero)]    simp [Nat.factorization_pow, hq.factorization_self,      Nat.factorization_eq_zero_of_not_dvd hnot']  have hbc : b + c = s := by    simpa [Nat.factorization_mul (by omega : x ≠ 0) (by omega : y ≠ 0),      Nat.factorization_mul (pow_ne_zero s hq.ne_zero) (pow_ne_zero t hp.ne_zero),      Nat.factorization_pow, hq.factorization_self,      Nat.factorization_eq_zero_of_not_dvd hnot', hxq, hyq] using hvq  exact ⟨b, c, hbc, hxb, hyc, hv⟩
See it in the graphDiscuss this resultChallenge it