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 leadingzeros. 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.∎