AFTD Auto-Formalizing Theoretical Domains

mondrian_two_prime_divisor_encoding

theoremverified

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

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.

  1. 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.

    lines 4–8

    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
  2. 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.

    lines 9–12

    uses Nat.ordCompl_dvd_ordCompl_of_dvd, Nat.mul_comm, Nat.ordCompl_pow_mul_of_not_dvd

      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
  3. 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.

    line 13

    uses Nat.dvd_prime_pow

      obtain ⟨b, hb, hxb⟩ := (Nat.dvd_prime_pow hq).mp hc
  4. x = 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)).

    lines 14–18

    uses Nat.ordProj_mul_ordCompl_eq_self, Nat.mul_comm

      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
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

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
See it in the graphDiscuss this resultChallenge it