corollary of Kummer’s theorem

As shown in Kummer’s theorem, the power of a prime number $p$ dividing$\left(\genfrac{}{}{0pt}{}{n}{m}\right),n\ge m\in \mathbb{N}$, was the total number of carries whenadding $m$ and $n-m$ in base $p$. We’ll give a recurrence relation for the carryindicator.

Given integers $n\ge m\ge 0$ and a prime number $p$, let $n_i,m_i,r_i$ bethe $i$-th digit of $n,m$, and $r:=n-m$, respectively.

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

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

For each $i\ge 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

$$\lfloor \frac{n}{p^i}\rfloor =\lfloor \frac{m}{p^i}\rfloor +\lfloor \frac{r}{p^i}\rfloor +c_{i-1}$$(1)

for all $i\ge 0$.