AFTD Auto-Formalizing Theoretical Domains

factorization_lt_of_is_m_number

theoremverified

If n is a positive M-number and p is prime, then n.factorization p < p.

Statement

theorem factorization_lt_of_is_m_number (n : ℕ) (hn : 0 < n) (hm : is_m_number n) (p : ℕ) (hp : p.Prime) :
    n.factorization p < p
Source
step towards strongly_matchable_of_is_m_number
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_m_numberA natural number n is an M-number if for every prime p, p^p does not divide n.

The proof, explained

The theorem is proved by contradiction. If the p-adic valuation of n at prime p were at least p, then p^p would divide n. However, this contradicts the assumption that n is an M-number, which requires that p^p does not divide n for any prime p.

  1. Assuming the negation of the goal, p ≤ n.factorization p.

    We proceed by contradiction and assume that n.factorization p < p does not hold. By Nat.le_of_not_lt, the negation of this strict inequality implies the reverse inequality p ≤ n.factorization p.

    lines 4–5

    uses Nat.le_of_not_lt

      by_contra h
      have hp_le : p ≤ n.factorization p := Nat.le_of_not_lt h
  2. A contradiction is reached, completing the proof.

    Because n > 0, n is non-zero by Nat.pos_iff_ne_zero.mp. For any prime p and non-zero n, Nat.Prime.pow_dvd_iff_le_factorization establishes that p^p divides n if and only if p ≤ n.factorization p. Since p ≤ n.factorization p holds, p^p must divide n. However, the hypothesis hm states that n is an M-number, which by definition means ¬(p^p ∣ n) for any prime p. This contradiction completes the proof.

    lines 6–7

    uses Nat.Prime.pow_dvd_iff_le_factorization, Nat.pos_iff_ne_zero.mp

      exact hm p hp
        ((Nat.Prime.pow_dvd_iff_le_factorization hp (Nat.pos_iff_ne_zero.mp hn)).mpr hp_le)
Nat.le_of_not_lt
For natural numbers a and b, if ¬(a < b), then b ≤ a.
Nat.Prime.pow_dvd_iff_le_factorization
For a prime p, an exponent k, and a non-zero natural number n, p^k divides n if and only if k ≤ n.factorization p.
Nat.pos_iff_ne_zero.mp
If a natural number is strictly positive, then it is non-zero (0 < n → n ≠ 0).

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 a positive integer n is an M-number, then its p-adic valuation at any prime p is strictly less than p. -/theorem factorization_lt_of_is_m_number (n : ℕ) (hn : 0 < n) (hm : is_m_number n) (p : ℕ) (hp : p.Prime) :    n.factorization p < p := by  by_contra h  have hp_le : p ≤ n.factorization p := Nat.le_of_not_lt h  exact hm p hp    ((Nat.Prime.pow_dvd_iff_le_factorization hp (Nat.pos_iff_ne_zero.mp hn)).mpr hp_le)
See it in the graphDiscuss this resultChallenge it