mondrian_distinct_prime_not_dvd_pow
A prime q distinct from p does not divide any power of p.
Statement
theorem mondrian_distinct_prime_not_dvd_pow (p q a : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hpq : p ≠ q) : ¬ q ∣ p ^ a- 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 2
- 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…
The proof, explained
We argue by contradiction: suppose q divides p ^ a. Since q is prime, it must divide the base p. Because p is also prime, its only divisors are 1 and p, forcing q = 1 or q = p. Both possibilities are impossible: q cannot be 1 because q is prime, and q cannot be p because p ≠ q by hypothesis.
Assuming for contradiction that q ∣ p ^ a, either q = 1 or q = p.
Suppose for contradiction that q ∣ p ^ a. Since q is prime, dividing a power p ^ a implies that q divides p itself (hq.dvd_of_dvd_pow). But p is also prime, so its only divisors are 1 and p (Nat.dvd_prime), leaving only two possibilities: q = 1 or q = p.
uses
Nat.dvd_prime,hq.dvd_of_dvd_powintro hh have := (Nat.dvd_prime hp).mp (hq.dvd_of_dvd_pow hh)
The case q = 1 is impossible.
We split into cases on q = 1 ∨ q = p. In the first case, q = 1 contradicts the fact that a prime number cannot equal 1 (hq.ne_one).
uses
hq.ne_onercases this with h | h · exact hq.ne_one h
The case q = p is impossible, completing the proof.
In the second case, q = p directly contradicts the hypothesis hpq that p ≠ q.
· exact hpq h.symm
Nat.dvd_prime- A natural number divides a prime p if and only if it is 1 or p.
hq.dvd_of_dvd_pow- If a prime divides a power m ^ n, then it divides m.
hq.ne_one- A prime number is not equal to 1.
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_distinct_prime_not_dvd_pow (p q a : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) : ¬ q ∣ p ^ a := by intro hh have := (Nat.dvd_prime hp).mp (hq.dvd_of_dvd_pow hh) rcases this with h | h · exact hq.ne_one h · exact hpq h.symm