mondrian_two_prime_divisor_encoding
Every 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.
Statement
theorem mondrian_two_prime_divisor_encoding (p q t s x : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hpq : p ≠ q) (hx : x ∣ q ^ s * p ^ t) :
∃ b ≤ s, x = q ^ b * p ^ (x.factorization p)- 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- Used by 3
- mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- mondrian_prime_free_height_two_chain_encodingIf 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.
- mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
The proof, explained
Every natural number x factors as the product of its p-part, p^(v_p(x)), and its prime-to-p part, x / p^(v_p(x)). Taking the prime-to-p part of the divisibility relation x ∣ q^s * p^t isolates the q-factor, showing that x / p^(v_p(x)) divides q^s. Since q is prime, this quotient must be a power q^b with b ≤ s, from which the factorization x = q^b * p^(v_p(x)) follows immediately.
p does not divide q
Suppose for contradiction that p divides q. Since q is prime (by Nat.dvd_prime), p must be either 1 or q. But p is prime, so p ≠ 1, and p ≠ q by hypothesis, giving a contradiction in both cases.
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
The prime-to-p part of x, namely x / p^(v_p(x)), divides q^s
Since x divides q^s * p^t, taking the prime-to-p component (the p-order complement) of both sides preserves divisibility (Nat.ordCompl_dvd_ordCompl_of_dvd). Factoring out the maximal power of p from p^t * q^s leaves q^s (Nat.ordCompl_pow_mul_of_not_dvd and Nat.mul_comm), because p is prime and does not divide q, so it cannot divide q^s. Replacing this in the divisibility statement shows that x / p^(v_p(x)) divides q^s.
uses
Nat.ordCompl_dvd_ordCompl_of_dvd,Nat.mul_comm,Nat.ordCompl_pow_mul_of_not_dvdhave hc := Nat.ordCompl_dvd_ordCompl_of_dvd hx p have he : (q ^ s * p ^ t) / p ^ ((q ^ s * p ^ t).factorization p) = q ^ s := by rw [Nat.mul_comm, Nat.ordCompl_pow_mul_of_not_dvd t hp (fun hh => hnot (hp.dvd_of_dvd_pow hh))] rw [he] at hc
x / p^(v_p(x)) = q^b for some exponent b ≤ s
Because q is prime and x / p^(v_p(x)) divides q^s, the only divisors of a prime power q^s are powers of q (Nat.dvd_prime_pow). Thus x / p^(v_p(x)) = q^b for some b ≤ s.
uses
Nat.dvd_prime_powobtain ⟨b, hb, hxb⟩ := (Nat.dvd_prime_pow hq).mp hcx = q^b * p^(v_p(x)), providing the desired witness b ≤ s
We choose b as the required exponent. Every number factors into its p-part times its prime-to-p part, so p^(v_p(x)) * (x / p^(v_p(x))) = x (Nat.ordProj_mul_ordCompl_eq_self). Substituting x / p^(v_p(x)) = q^b and commuting factors (Nat.mul_comm) gives x = q^b * p^(v_p(x)).
uses
Nat.ordProj_mul_ordCompl_eq_self,Nat.mul_commrefine ⟨b, hb, ?_⟩ have hr := Nat.ordProj_mul_ordCompl_eq_self x p change p ^ (x.factorization p) * (x / p ^ (x.factorization p)) = x at hr rw [hxb] at hr simpa only [Nat.mul_comm] using hr.symm
Nat.dvd_prime- A number divides a prime p if and only if it is equal to 1 or p.
Nat.dvd_prime_pow- For any prime p, the divisors of p^m are precisely the powers p^k with k ≤ m.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.ordCompl_dvd_ordCompl_of_dvd- If a divides b, then the prime-to-p part of a divides the prime-to-p part of b.
Nat.ordCompl_pow_mul_of_not_dvd- If p is prime and does not divide m, then removing the maximal power of p from p^k * m leaves m.
Nat.ordProj_mul_ordCompl_eq_self- Every natural number n decomposes as the product of its p-power factor p^(v_p(n)) and its prime-to-p part n / p^(v_p(n)).
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_divisor_encoding (p q t s x : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (hx : x ∣ q ^ s * p ^ t) : ∃ b ≤ s, x = q ^ b * p ^ (x.factorization p) := by 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 hc := Nat.ordCompl_dvd_ordCompl_of_dvd hx p have he : (q ^ s * p ^ t) / p ^ ((q ^ s * p ^ t).factorization p) = q ^ s := by rw [Nat.mul_comm, Nat.ordCompl_pow_mul_of_not_dvd t hp (fun hh => hnot (hp.dvd_of_dvd_pow hh))] rw [he] at hc obtain ⟨b, hb, hxb⟩ := (Nat.dvd_prime_pow hq).mp hc refine ⟨b, hb, ?_⟩ have hr := Nat.ordProj_mul_ordCompl_eq_self x p change p ^ (x.factorization p) * (x / p ^ (x.factorization p)) = x at hr rw [hxb] at hr simpa only [Nat.mul_comm] using hr.symm