mondrian_two_prime_factor_pair_encoding
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
- mondrian_two_prime_divisor_encodingEvery divisor x of q^s times p^t, for distinct primes p and q, is q^b times p to the p-adic exponent of x, with b at most s.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 4
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- mondrian_prime_square_area_middle_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square…
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
- mondrian_prime_free_factor_pair_encodingIn 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…
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.
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)).
uses
mondrian_two_prime_divisor_encodingobtain ⟨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]⟩
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.
uses
Nat.dvd_primehave 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
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.
uses
congrArghave hvp := congrArg (fun z : ℕ => z.factorization p) hxy have hvq := congrArg (fun z : ℕ => z.factorization q) hxy
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.
uses
Nat.factorization_mul,pow_ne_zero,Nat.factorization_pow,Nat.factorization_eq_zero_of_not_dvdhave 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
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.
uses
Nat.factorization_mul,pow_ne_zero,Nat.factorization_pow,Nat.factorization_eq_zero_of_not_dvdhave 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']
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.
uses
Nat.factorization_mul,pow_ne_zero,Nat.factorization_pow,Nat.factorization_eq_zero_of_not_dvdhave 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
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.
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.
- The notation `n.factorization p` represents the p-adic valuation v_p(n), which is the exponent of the prime p in the prime factorization of n.
- Automated tactics (`simpa`, `omega`, `nlinarith`) are used to discharge linear arithmetic on exponents, nonzeroness side conditions, and the commutativity of multiplication.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩