= Kummer's theorem
{c}
{title2=$v_p\binom nk=(d_p(k)+d_p(n-k)-d_p(n))/(p-1)$}
{wiki}
For a <prime number> $p$ and <integers> $0\leq k\leq n$, the <P-adic valuation> of the <binomial coefficient> $\binom nk$ equals the number of <arithmetic carries> in the base-$p$ <addition> of $k$ and $n-k$.<Number Theory for Mathematical Contests by David Anthony Santos>[David A. Santos, Number Theory for Mathematical Contests, revision 31 October 2007, §8.3, Theorem 246, printed p. 90: carry count for a binomial coefficient]{ref} Indeed, subtract the two denominator <factorial> valuations in the <Legendre formula>:
$$
v_p\binom nk=v_p(n!)-v_p(k!)-v_p((n-k)!)
=\frac{d_p(k)+d_p(n-k)-d_p(n)}{p-1}.
$$
Each <arithmetic carry> accounts for one unit of this quotient by <subadditivity of the base-p digit sum>. In particular, the <binomial coefficient> is divisible by $p$ exactly when at least one carry occurs.
For $n=50,k=17,p=3$, the <factorial> counts give
$$
v_3\binom{50}{17}=22-(5+1)-(11+3+1)=1.
$$
The matching <base-p expansions> are $17=(0122)_3$ and $33=(1020)_3$. Their units add to two; the next column gives $2+2=4=1+3$, sending one carry into the nines column. That column then gives $1+0+1=2$, and no further carry occurs. The result is $(1212)_3=50$. The <base-p digit sums> check the same result: $(5+3-6)/(3-1)=1$. Consequently $\binom{50}{17}$ is divisible by three but not by nine.
\Image[/legendre-base-three-digits-and-carry.png]
{title=The <base-p digit sum> and one <arithmetic carry> recover the same <prime exponents>}
{description=On the left, the <base-p expansion> $50=(1212)_3$ gives $v_3(50!)=(50-6)/2=22$. On the right, $(0122)_3+(1020)_3=(1212)_3$ has exactly one carry, from the threes column into the nines column. <Kummer's theorem> therefore gives $v_3\binom{50}{17}=1$.}
Back to article page
