# 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$. Dec 16, 2013 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). Dec 16, 2013 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. Jan 30, 2014 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. Jan 30, 2014 at 5:15
• This is probably a bit late to comment; but isn't ${0 \choose 1}$ equal to $0$ by definition? In that case, there is no contradiction. Mar 7, 2023 at 5:52

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