# highest power of prime $p$ dividing $\binom{m+n}{n}$

How to prove the theorem stated here.

Theorem. (Kummer, 1854) Let $p$ be a prime. The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ and $n$ in base $p$.

So far, I know if $m+n$ can be expanded in base power as $$m+n= a_0 + a_1 p + \dots +a_k p^k$$ and $m$ have to coefficients $\{ b_0 , b_1 , \dots b_i\}$ and $n$ can be expanded with coefficients $\{c_0, c_1 ,\dots , c_j\}$ in base $p$ then the highest power of prime that divides $\binom{m+n}{n}$ can be expressed as $$e = \frac{(b_0 + b_1 + \dots b_i )+ (c_0 + c_1 + \dots c_j )-(a_0 + a_1 + \dots a_k )}{p-1}$$ It follows from here page number $4$. But how does it relate to the number of carries? I am not being able to connect. Perhaps I am not understanding something very fundamental about addition.

• If there were no carries, you would have $a_i=b_i+c_i$ for all $i$, and consequently $e=0$. If $j$ is the least significant position with a carry, you get $a_j=b_j+c_j-p$ instead, and the carry will increase $a_{j+1}$ by one, so $e$ increases by $1$. It gets a bit more involved, if that carry causes an avalanche of further carries, but it all works out, if you continue the analysis. – Jyrki Lahtonen Jun 14 '14 at 9:17
• @JyrkiLahtonen thank you very much for answer. it makes sense. – Mula Ko Saag Jun 14 '14 at 9:21
• Some related posts: math.stackexchange.com/questions/609078/… and math.stackexchange.com/questions/51469/… – Martin Sleziak Jun 14 '14 at 9:23

## 2 Answers

If $b_{0} + c_{0} < p$, then $a_{0} = b_{0} + c_{0}$, there are no carries, and the term $$b_{0} + c_{0} - a_{0} = 0$$ does not contribute to your $e$.

If $b_{0} + c_{0} \ge p$, then $a_{0} = b_{0} + c_{0} - p$, and this time $b_{0} + c_{0} - a_{0}$ gives a contribution of $p$ to the numerator of $e$. Plus, there is a contribution of $1$ to $a_{1}$, so the net contribution to the numerator of $e$ is $p -1$, and that to $e$ is $1$. Repeat.

As mentioned by Jyrki Lahtonen in his comment (which appeared while I was typesetting this answer), you may have propagating carries, but this is the basic argument.

• +1, of course. This time I was extra reluctant to post that comment as an answer. You see, certain filtrations of modules that I studied in my dissertation back in the day depended on this formula. So initially I was a bit ashamed for not being able to give a detailed road map :-). The OP is happy, so ... – Jyrki Lahtonen Jun 14 '14 at 9:34
• @JyrkiLahtonen, thanks. Me, I am slightly embarassed, because all I say here was already in your comment. But then sometimes I find myself in your shoes (I post comment, somebody else posts answer), so... – Andreas Caranti Jun 14 '14 at 9:39
• @AndreasCaranti I'm sorry, but I do not understand. What "carry" exactly means? – byk7 May 1 '18 at 11:14
• @byk7 it should translate to přenést. – Andreas Caranti May 1 '18 at 12:24

Rubbing the remaining brain cells together real hard did bring to the surface the following argument that generalizes Kummer's Theorem to multinomial coefficients.

Let the base-$p$ expansions of non-negative integers $n_i, i=1,2,\ldots,k$ and $n=\sum_{i=1}^kn_i$ be $$n_i=\sum_{j=0}^\infty b_{i,j}p^j,\qquad n=\sum_{j=0}^\infty a_jp^j.$$ Consider the multinomial coefficient $${n\choose n_1,n_2,\ldots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$

As in the case of binomial coefficients (write the multinomial coefficient as a product of binomial coefficients in the usual way) we see that the highest power, $p^e$, dividing the multinomial coefficient is determined by the formula $$e=\frac{\sum_{i=1}^k\sum_j b_{i,j}-\sum_j a_j}{p-1}.\qquad(*)$$

Assume that we are doing the grade school addition of the sum $n_1+n_2+\cdots+n_k=n$. Let the carry at position $j$, $j=0,1,\ldots$, be $c_j$. Because we are dealing with integers, there is no initial carry, so we declare $c_{-1}=0$. The addition algorithm for the digit at position $j$ amounts to the equation $$\sum_{i=1}^kb_{i,j}+c_{j-1}=pc_j+a_j,$$ or, equivalently, to the equation $$\left(\sum_{i=1}^kb_{i,j}\right)-a_j=pc_j-c_{j-1}$$ that holds for all $j\ge0$.

Adding all these equations together shows that numerator in the formula $(*)$ for $e$ is \begin{aligned} \sum_{i=1}^k\sum_j b_{i,j}-\sum_j a_j&=\sum_{j=0}^{j_{MAX}}(pc_j-c_{j-1})\\ &=pc_{j_{MAX}}+\sum_{j=0}^{j_{MAX}-1}(p-1)c_j-c_{-1}\\ &=(p-1)\sum_jc_j, \end{aligned} because clearly at the most significant digit there will be no further carry, $c_{j_{MAX}}=0$, and because $c_{-1}=0$. Thus we can rewrite formula $(*)$ to read $$e=\sum_j c_j.$$ In other words $e$ equals the total carry $\sum_j c_j$.