TAOCP 1.2.6 Exercise 11

Let v_p(m) denote the exponent of the highest power of $p$ dividing $m$, and let

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 11. [M20] (E. Kummer, 1852.) Let $p$ be prime. Show that if $p^n$ divides $\binom{a+b}{a}$ but $p^{n+1}$ does not, then $n$ is equal to the number of carries that occur when $a$ is added to $b$ in the $p$-ary number system.

Verified: yes
Solve time: 2m16s

Solution

Let

$$ v_p(m) $$

denote the exponent of the highest power of $p$ dividing $m$, and let

$$ s_p(n) $$

denote the sum of the digits of $n$ written in base $p$.

We shall compute

$$ v_p!\binom{a+b}{a} $$

using Legendre's formula and then relate the result to the number of carries in the base-$p$ addition of $a$ and $b$.

Step 1. Legendre's formula

For every nonnegative integer $N$,

$$ v_p(N!)=\sum_{k\ge1}\left\lfloor \frac{N}{p^k}\right\rfloor =\frac{N-s_p(N)}{p-1}. $$

Therefore

$$ v_p!\binom{a+b}{a} =v_p((a+b)!)-v_p(a!)-v_p(b!). $$

Substituting Legendre's formula gives

$$ v_p!\binom{a+b}{a} = \frac{a+b-s_p(a+b)}{p-1} -\frac{a-s_p(a)}{p-1} -\frac{b-s_p(b)}{p-1}. $$

The terms $a+b-a-b$ cancel, yielding

$$ v_p!\binom{a+b}{a} = \frac{s_p(a)+s_p(b)-s_p(a+b)}{p-1}. \tag{1} $$

Thus it remains to show that

$$ s_p(a)+s_p(b)-s_p(a+b) $$

is equal to $(p-1)$ times the number of carries occurring when $a$ and $b$ are added in base $p$.

Step 2. Effect of a carry on the digit sum

Write

$$ a=\sum_{i\ge0} a_i p^i,\qquad b=\sum_{i\ge0} b_i p^i, $$

with $0\le a_i,b_i<p$.

Let $r_i\in{0,1}$ be the carry from position $i$ to position $i+1$, and set $r_{-1}=0$. If

$$ a+b=\sum_{i\ge0} c_i p^i, $$

then at each digit position,

$$ a_i+b_i+r_{i-1}=c_i+p,r_i. \tag{2} $$

Summing (2) over all $i$ gives

$$ \sum_i a_i+\sum_i b_i+\sum_i r_{i-1} = \sum_i c_i+p\sum_i r_i. $$

Since $r_{-1}=0$ and only finitely many carries occur,

$$ \sum_i r_{i-1}=\sum_i r_i. $$

Hence

$$ s_p(a)+s_p(b)-s_p(a+b) = (p-1)\sum_i r_i. \tag{3} $$

But $\sum_i r_i$ is exactly the number of carries that occur in the base-$p$ addition of $a$ and $b$. Let this number be $N$. Then (3) becomes

$$ s_p(a)+s_p(b)-s_p(a+b) =(p-1)N. $$

Substituting into (1) yields

$$ v_p!\binom{a+b}{a} = \frac{(p-1)N}{p-1} = N. $$

Therefore the exponent of $p$ in $\binom{a+b}{a}$ is exactly the number of carries in the base-$p$ addition of $a$ and $b$.

Consequently, if

$$ p^n\mid \binom{a+b}{a} \qquad\text{but}\qquad p^{n+1}\nmid \binom{a+b}{a}, $$

then

$$ n=v_p!\binom{a+b}{a}, $$

which equals the number of carries occurring when $a$ is added to $b$ in the $p$-ary number system.

$\square$