5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\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$ Commented Jun 14, 2014 at 9:17
  • $\begingroup$ @JyrkiLahtonen thank you very much for answer. it makes sense. $\endgroup$ Commented Jun 14, 2014 at 9:21
  • $\begingroup$ Some related posts: math.stackexchange.com/questions/609078/… and math.stackexchange.com/questions/51469/… $\endgroup$ Commented Jun 14, 2014 at 9:23

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\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$ Commented Jun 14, 2014 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$ Commented Jun 14, 2014 at 9:39
  • $\begingroup$ @AndreasCaranti I'm sorry, but I do not understand. What "carry" exactly means? $\endgroup$
    – byk7
    Commented May 1, 2018 at 11:14
  • $\begingroup$ @byk7 it should translate to přenést. $\endgroup$ Commented May 1, 2018 at 12:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .