# Divisibility of binomial coefficient by prime power - Kummer's theorem

Let's say we have binomial coefficient $\binom{n}{m}$. And we need to find the greatest power of prime $p$ that divides it.

Usually Kummer's theorem is stated in terms of the number of carries you perform while adding $m$ and $n-m$ in base $p$.

I found an equivalent statement of this theorem that reads like this: if we write $$\binom{n}{m}\equiv\binom{n_0}{m_0}\binom{n_1}{m_1}\ldots\binom{n_d}{m_d}\pmod{p},$$ where $n = n_0 + n_1p + n_2p^2 + \ldots + n_dp^d$ and $m = m_0 + m_1p + m_2p^2 + \ldots + m_dp^d$, then the power dividing $\binom{n}{m}$ is precisely the number of indicies $i$ for which $n_i<m_i$.

Now let's take an example. Let's look at $\binom{25}{1}$ and $p=5$. We have $$\binom{25}{1}\equiv\binom{1}{0}\binom{0}{0}\binom{0}{1}\pmod{5}.$$ We have only one index $i$ for which $n_i < m_i$, which is the last one. This suggests that $\binom{25}{1}$ can't be divided by $25$, which obviously isn't true.

Where's the problem? In case you wonder where I found this statement of Kummer's theorem, here is the link: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf

Thank you!

• ... while adding $m$ and $n-m$, not $n$ and $n-m$. – Robert Israel Dec 16 '13 at 14:07
• As we all learned in grade school adding one may lead to an avalanche of carries. Therefore that "equivalent" statement is wrong (and not equivalent at all). – Jyrki Lahtonen Dec 16 '13 at 14:19
• The answer by user124881 is correct: this is a mistake in the PDF you linked, and it doesn't appear in the published version. Possibly even better than the published version (because it might get updated) is the online (not PDF) version; see here and here. Both the book and online version omit the "precisely the number of indices $i$ for which $n_i < m_i$" sentence. – ShreevatsaR Jan 30 '14 at 5:14
• By the way, the statement that $\binom{n}{m} \equiv \binom{n_0}{m_0}\binom{n_1}{m_1}\cdots\binom{n_d}{m_d} \pmod p$ is true, however. – ShreevatsaR Jan 30 '14 at 5:15

## 1 Answer

I've noticed this, too. I believe that you're correct and that Granville's "equivalent statement of this theorem" is wrong.

As evidence, I give you two items: first, the counter-example you mentioned, and second, the published version of your linked article by Andrew Granville does not contain this line that "the power dividing $n\choose{m}$ is precisely the number of indicies $i$ for which $n_i < m_i$."

The published version is a bit hard to find, but here's a version on Google Books that I found by Googling "Andrew Granville Binomial Coefficients" from within Google Books. You'll noticed that this published version is an edited copy of the article on the Univ. of Montreal website.

When in doubt, look for the official version of the article. My guess is that the article on Andrew's Montral website is a slightly earlier, unedited version.

EDIT: I just got an e-mail from Andrew himself on this question, and he said, "You should believe the published version -- I do vaguely remember making such a a change. Thanks for pointing out the discrepancy."