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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 14 '14 at 9:17
  • $\begingroup$ @JyrkiLahtonen thank you very much for answer. it makes sense. $\endgroup$ – Mula Ko Saag Jun 14 '14 at 9:21
  • $\begingroup$ Some related posts: math.stackexchange.com/questions/609078/… and math.stackexchange.com/questions/51469/… $\endgroup$ – Martin Sleziak Jun 14 '14 at 9:23

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.

  • $\begingroup$ +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 ... $\endgroup$ – Jyrki Lahtonen Jun 14 '14 at 9:34
  • 1
    $\begingroup$ @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... $\endgroup$ – Andreas Caranti Jun 14 '14 at 9:39
  • $\begingroup$ @AndreasCaranti I'm sorry, but I do not understand. What "carry" exactly means? $\endgroup$ – byk7 May 1 '18 at 11:14
  • $\begingroup$ @byk7 it should translate to přenést. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.