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 Now let's take an example. Let's look at $\binom{25}{1}$ and $p=5$. We have 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!
$$
\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
$$
\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.
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."
No comments:
Post a Comment