factorization_lt_of_is_m_number
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.
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.
uses
Nat.le_of_not_ltby_contra h have hp_le : p ≤ n.factorization p := Nat.le_of_not_lt h
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.
uses
Nat.Prime.pow_dvd_iff_le_factorization,Nat.pos_iff_ne_zero.mpexact 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
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.
/-- 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)