AFTD Auto-Formalizing Theoretical Domains

mondrian_distinct_prime_not_dvd_pow

theoremverified

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

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.

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

    lines 3–4

    uses Nat.dvd_prime, hq.dvd_of_dvd_pow

      intro hh
      have := (Nat.dvd_prime hp).mp (hq.dvd_of_dvd_pow hh)
  2. 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).

    lines 5–6

    uses hq.ne_one

      rcases this with h | h
      · exact hq.ne_one h
  3. The case q = p is impossible, completing the proof.

    In the second case, q = p directly contradicts the hypothesis hpq that p ≠ q.

    line 7

      · 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

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