AFTD Auto-Formalizing Theoretical Domains

is_m_number_of_dvd_not_dvd_pow

theoremverified

For natural numbers d, n, and p, if d divides n, every prime q such that q^q divides n satisfies q = p, and p^p does not divide d, then d is an M-number.

Statement

theorem is_m_number_of_dvd_not_dvd_pow {d n p : ℕ} (hdn : d ∣ n)
    (h_uniq : ∀ q : ℕ, q.Prime → q ^ q ∣ n → q = p)
    (h_not : ¬ p ^ p ∣ d) :
    is_m_number d
Source
arXiv:2610.37512, Section 6, proof of Corollary 1.4
Verified
29 Oct 2026
Axioms
propext
Built on 1
  • is_m_numberA natural number n is an M-number if for every prime p, p^p does not divide n.

Read back from the Lean

For all natural numbers $d$, $n$, and $p$, if $d$ divides $n$, and every prime $q$ such that $q^q$ divides $n$ is equal to $p$, and $p^p$ does not divide $d$, then $d$ is an m-number.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that d is an M-number, we suppose for contradiction that some prime q satisfies q^q ∣ d. Because d divides n, transitivity of divisibility implies q^q ∣ n, which by the uniqueness hypothesis forces q = p. Thus p^p ∣ d, directly contradicting the assumption that p^p does not divide d.

  1. Assume for contradiction that there exists a prime q such that q^q divides d.

    By definition, d is an M-number if no prime q satisfies q^q ∣ d. Unfolding this definition, we fix an arbitrary prime q and assume q^q ∣ d, aiming to derive a contradiction (False).

    line 6

      intro q hq hq_pow
  2. The prime q must equal p.

    Since q^q ∣ d and d ∣ n, divisibility is transitive (dvd_trans), which implies q^q ∣ n. By the uniqueness hypothesis, any prime whose self-power divides n must equal p, so q = p.

    lines 7–8

    uses dvd_trans

      have hqn : q ^ q ∣ n := dvd_trans hq_pow hdn
      have heq : q = p := h_uniq q hq hqn
  3. A contradiction is reached, completing the proof.

    Substituting q = p into the hypothesis q^q ∣ d gives p^p ∣ d. This directly contradicts the assumption that p^p does not divide d.

    lines 9–10

      subst heq
      exact h_not hq_pow
dvd_trans
Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.

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

/-- If all prime powers q^q dividing n have q = p, and p^p does not divide d for a divisor d of n, then d is an M-number. -/theorem is_m_number_of_dvd_not_dvd_pow {d n p : ℕ} (hdn : d ∣ n)    (h_uniq : ∀ q : ℕ, q.Prime → q ^ q ∣ n → q = p)    (h_not : ¬ p ^ p ∣ d) :    is_m_number d := by  intro q hq hq_pow  have hqn : q ^ q ∣ n := dvd_trans hq_pow hdn  have heq : q = p := h_uniq q hq hqn  subst heq  exact h_not hq_pow
See it in the graphDiscuss this resultChallenge it