Legendre's formula
ProvedFamousTheorems.legendre_formulaLegendre's formula. For a prime and a natural number , the exponent of in is
The sum is finite since the terms vanish once . The formula counts multiples of up to . It gives the number of trailing zeros of and is used in estimates for binomial coefficients, such as in Chebyshev's and Erdős's proofs of Bertrand's postulate. An equivalent form is , with the base- digit sum.
Formalization note. Mathlib's padicValNat_factorial. The sum runs over Finset.Ico 1 b for any b with , and n / p ^ i is natural-number (floor) division.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem legendre_formula {p n b : ℕ} [Fact p.Prime] (hnb : Nat.log p n < b) :
padicValNat p n.factorial = ∑ i ∈ Finset.Ico 1 b, n / p ^ i := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `padicValNat_factorial`. Proof here reduces to that Mathlib result.