# Kummer’s theorem

Given integers $n\geq m\geq 0$ and a prime number $p$, then the power of $p$ dividing $\binom{n}{m}$ is equal to the number of carries when adding $m$ and $n-m$ in base $p$.

###### Proof.

For the proof we can allow of numbers in base $p$ with leading zeros. So let

 $\displaystyle n_{d}n_{d-1}\cdots n_{0}$ $\displaystyle:=n,$ $\displaystyle m_{d}m_{d-1}\cdots m_{0}$ $\displaystyle:=m,$

all in base $p$. We set $r=n-m$ and denote the $p$-adic representation of $r$ with $r_{d}r_{d-1}\cdots r_{0}$.

We define $c_{-1}=0$, and for each $0\leq j\leq d$

 $c_{j}=\begin{cases}1&\text{for m_{j}+r_{j}\geq p}\\ 0&\text{otherwise.}\end{cases}$ (1)

Finally, we introduce $\delta_{p}(n)$ as the sum of digits in the $p$-adic of $n$. Then it follows that the power of $p$ dividing $\binom{n}{m}$ is

 $\frac{\delta_{p}(m)+\delta_{p}(r)-\delta_{p}(n)}{p-1}.$

For each $j\geq 0$, we have

 $n_{j}=m_{j}+r_{j}+c_{j-1}-p.c_{j}.$

Then

 $\displaystyle\delta_{p}(m)+\delta_{p}(r)-\delta_{p}(n)$ $\displaystyle=\sum_{k=0}^{d}\left(m_{k}+r_{k}-n_{k}\right)$ $\displaystyle=\sum_{k=0}^{d}\left((p-1)c_{j}\right)$ $\displaystyle+\sum_{k=0}^{d}\left(c_{j}-c_{j-1}\right)$ $\displaystyle=\sum_{k=0}^{d}(p-1)c_{j}$ $\displaystyle+c_{d}-c_{-1}$

This gives us

 $\frac{\delta_{p}(m)+\delta_{p}(r)-\delta_{p}(n)}{p-1}=\sum_{k=0}^{d}c_{k},$

the total number of carries. ∎

Title Kummer’s theorem KummersTheorem 2013-03-22 13:22:37 2013-03-22 13:22:37 Thomas Heye (1234) Thomas Heye (1234) 14 Thomas Heye (1234) Theorem msc 11A63