# 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

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