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
Canonical name	KummersTheorem
Date of creation	2013-03-22 13:22:37
Last modified on	2013-03-22 13:22:37
Owner	Thomas Heye (1234)
Last modified by	Thomas Heye (1234)
Numerical id	14
Author	Thomas Heye (1234)
Entry type	Theorem
Classification	msc 11A63