corollary of Kummer’s theorem

As shown in Kummer’s theorem, the power of a prime number $p$ dividing $\binom{n}{m},n\geq m\in\mathbb{N}$ , was the total number of carries when adding $m$ and $n-m$ in base $p$ . We’ll give a recurrence relation for the carry indicator.

Given integers $n\geq m\geq 0$ and a prime number $p$ , let $n_{i},m_{i},r_{i}$ be the $i$ -th digit of $n, m$ , and $r:=n-m$ , respectively.

Define $c_{-1}=0$ , and

c_{i}=\begin{cases}1&\text{if $m_{i}+r_{i}\geq p$,}\\ 0&\text{otherwise}\end{cases}

for each $i\geq 0$ up to the number of digits of $n$ .

For each $i\geq 0$ we have

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

Starting with the $i$ -th digit of $n$ , we multiply with increasing powers of $p$ to get

\sum_{k=i}^{d}n_{k}p^{k-i}=\left(\sum_{k=i}^{d}p^{k-i}(m_{k}+r_{k})\right)+% \sum_{k=i}^{d}\left(p^{k-1-(i-1)}c_{k-1}-p^{k-(i-1)}c_{k}\right).

The last sum in the above equation leaves only the values for indices $i$ and $d$ , and we get

\left\lfloor\frac{n}{p^{i}}\right\rfloor=\left\lfloor\frac{m}{p^{i}}\right% \rfloor+\left\lfloor\frac{r}{p^{i}}\right\rfloor+c_{i-1}

(1)

for all $i\geq 0$ .

Title	corollary of Kummer’s theorem
Canonical name	CorollaryOfKummersTheorem
Date of creation	2013-03-22 13:23:07
Last modified on	2013-03-22 13:23:07
Owner	Thomas Heye (1234)
Last modified by	Thomas Heye (1234)
Numerical id	7
Author	Thomas Heye (1234)
Entry type	Corollary
Classification	msc 11A63