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 CorollaryOfKummersTheorem 2013-03-22 13:23:07 2013-03-22 13:23:07 Thomas Heye (1234) Thomas Heye (1234) 7 Thomas Heye (1234) Corollary msc 11A63