3.2 p-adic valuation of binomial coefficients

Lemma 3.3 logn of binomial via factorials

✓

For prime \(p\) and \(k \leq n\),

\[ v_p\! \binom {n}{k} = v_p(n!) - v_p(k!) - v_p((n-k)!). \]

Proof. From \(\binom {n}{k} \cdot k! \cdot (n-k)! = n!\) (Lemma 1.10), apply \(v_p\) to both sides using multiplicativity (Lemma 1.3), noting that all factors are positive by Lemmas 1.11 and 1.12.

Lemma 3.4 logn of binomial via Legendre sums

✓

For prime \(p\), \(k \leq n\), and \(b {\gt} \texttt{trunc\_ log}(p, n)\),

\[ 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 . \]

Proof. Substitute Lemma 3.2 (applied to \(n\), \(k\), and \(n-k\), all with the same bound \(b\)) into Lemma 3.3.