Kummer's theorem on binomial coefficients
ProvedFamousTheorems.kummer_theorem_binomialKummer's theorem. Let be a prime and . The exponent of in equals the number of carries when and are added in base :
In particular exactly when adding and in base produces a carry. Together with Lucas's theorem this gives the arithmetic of binomial coefficients modulo prime powers. It is used, for example, in studying the divisibility of central binomial coefficients.
Formalization note. Mathlib's padicValNat_choose. The carry positions are counted over Finset.Ico 1 b for any b with , which covers all digit positions. The -th test p ^ i ≤ k % p ^ i + (n - k) % p ^ i is exactly a carry out of the -th lowest digit.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem kummer_theorem_binomial {p n k b : ℕ} [Fact p.Prime] (hkn : k ≤ n) (hnb : Nat.log p n < b) :
padicValNat p (n.choose k) =
((Finset.Ico 1 b).filter fun i => p ^ i ≤ k % p ^ i + (n - k) % p ^ i).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `padicValNat_choose`. Proof here reduces to that Mathlib result.