4 Kummer’s theorem
Let \(p\) be prime and \(0 \leq k \leq n\). Then
\[ v_p\! \binom {n}{k} = \sum _{i=1}^{b} \mathrm{carry}(p, i, k, n-k), \]
for any \(b {\gt} \texttt{trunc\_ log}(p, n)\). Equivalently, the \(p\)-adic valuation of \(\binom {n}{k}\) equals the number of carries when adding \(k\) and \(n-k\) in base \(p\). Proof. By Lemma 3.4,
\[ v_p\! \binom {n}{k} = \sum _{i=1}^{b} \left\lfloor \frac{n}{p^i} \right\rfloor - \sum _{i=1}^{b} \left\lfloor \frac{k}{p^i} \right\rfloor - \sum _{i=1}^{b} \left\lfloor \frac{n-k}{p^i} \right\rfloor . \]
By Lemma 2.8, the difference of the three Legendre sums equals the carry count.
For prime \(p\), \(k \leq n\), and \(b {\gt} \texttt{trunc\_ log}(p, n)\),
\[ v_p\! \binom {n}{k} = \# \bigl\{ i \in \{ 1, \ldots , b\} \; \big|\; \mathrm{carry}(p, i, k, n-k) \bigr\} . \]
Proof. Since \(\mathrm{carry}\) is boolean, summing it over \(\{ 1, \ldots , b\} \) equals the cardinality of the set where it holds.