# Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the numerator is divisible by $p$ whereas the denominator is not (since it is a product of numbers smaller than $p$ and $p$ is prime).

My problem is with generalizing this argument for $q=p^n$. I'm looking for the most elegant and simple way to prove that $p$ still divides $\large q\choose i$.

-
The most general result of this nature tells us that the exact power of $p$ that divides a binomial coefficient $n \choose k$ is the sum of the carries, when we write both $k$ and $n-k$ in base $p$, and add them using the grade school algorithm. When $n$ is a power of $p$ there will always be some carry, because the result of the addition has so many trailing zeros in base $p$. Proof follows from the stuff presented by Bruno Joyal below. –  Jyrki Lahtonen Jul 14 '11 at 21:15

Let $v_p(n)$ denotes the exponent of the largest power of $p$ which divides $n$. We'll show that $v_p\left({p^n \choose i}\right) = n-v_p(i)$. In particular, this is positive unless $i=0$ or $i=p^n$.

It's easy to see that for any $n$, $$v_p(n!)=\sum_{k=1}^\infty \left\lfloor \frac{n}{p^k}\right\rfloor.$$

We need an expression for $v_p(q!)-v_p(i!)-v_p((q-i)!)$, where $q=p^n$.

Notice that $v_p(q!) = \frac{p^n-1}{p-1}$ by the above formula (which just becomes a geometric series with finitely many terms).

Notice also that for any $x \in \mathbb{R}$, $\lfloor -x \rfloor + \lfloor x \rfloor =\begin{cases} 0 && \text{if } x \in \mathbb{Z} \\ -1 && \text{otherwise.}\end{cases}$

Therefore,

\begin{align}v_p((q-i)!)+v_p(i!) &= \sum_{k=1}^n \left\lfloor\frac{p^n-i}{p^k}\right\rfloor + \left\lfloor\frac{i}{p^k}\right\rfloor \\ &=\sum_{k=1}^n \left(p^{n-k} + \left\lfloor\frac{-i}{p^k}\right\rfloor + \left\lfloor\frac{i}{p^k}\right\rfloor\right) \\&=\frac{p^n-1}{p-1}-(n-v_p(i)).\end{align}

Hence we have $v_p\left({p^n \choose i}\right) = n-v_p(i)$.

Edit (Dec. 6 2011): for fun, yesterday I asked myself how badly the equality $v_p\left({n \choose m}\right) = v_p(n)-v_p(m)$ fails for general $n$ and $m$. So I used Mathematica to create the following image. The triangle consists of the first 256 rows of Pascal's triangle, colored using the following rule: the greener a points is, the bigger the difference $v_2\left({n \choose m}\right) - v_2(n) +v_2(m)$. A little experimentation shows that any other choice of prime generates a similar image.

To create this image, I used the p-adic arithmetic package and the following code:

p = 2; until = 256; t = Table[Table[{RGBColor[0, PadicOrder[Binomial[n, m]/(n/m), p]/Log[p, until], 0], Rectangle[{until/2 - 1/2 - n/2 + m, n}]}, {m, 1, n}], {n, 1, until}]; Graphics[t]

-
Beautiful pic! If it's not a secret, could you share the Mathematica code you used? –  Ｊ. Ｍ. Dec 7 '11 at 3:45
@J.M. Thank you J.M.! With pleasure, I will add it in right away. –  Bruno Joyal Dec 7 '11 at 3:55
@J.M. Code should never be secret, unless it's a secret code. –  Bruno Joyal Dec 7 '11 at 4:02
You have it backwards; thank you for the answer, the picture, and the code. –  Ｊ. Ｍ. Dec 7 '11 at 4:42
Indeed! If I had coloured it with just one tone of green, it would be Pascal's triangle mod $2$, which also looks like the Sierpinski triangle. But I like this one better, it almost looks 3D if I stare at it long enough. :) –  Bruno Joyal Dec 7 '11 at 5:30

How about using the fact that $(x+y)^p = x^p + y^p$ in a field of characteristic $p$? This follows from the fact you just stated. Now keep repeating it to prove that $(x+y)^q = x^q + y^q$ for any $q = p^n$.

-
Can you elaborate what you mean by "repeat"? –  Gadi A Jul 14 '11 at 18:49
Ok, I got it, your solution is quite elegant. Thanks! –  Gadi A Jul 14 '11 at 19:13
However, I'm not sure if it proves what I asked (although the identity above is what I was really after). How it shows that all the intermediate coefficients are divisible by q? They might have simply canceled each other out. –  Gadi A Jul 14 '11 at 19:14
@Gadi, the intermediate coefficients may not all be divisible by $q$, but they are all divisible by $p$, so the equation holds in any field of characteristic $p$. –  Gerry Myerson Jul 15 '11 at 1:32
@Gadi, if you're worried about cancellation, you can work with the field Z/p(x,y), where x and y are transcendentals. –  Steven Sam Jul 16 '11 at 17:22

$$\binom qi=\frac{\prod_{k=0}^{i-1}(q-k)}{\prod_{k=1}^i k}=\frac qi\prod_{k=1}^{i-1}\frac{q-k}k\;.$$

There is at least one factor of $p$ in $q/i$, and each of the factors in the remaining product has the same number of factors of $p$ in the numerator and the denominator.

[Edit in response to the comment:] Let $j$ be the number of factors of $p$ in $k$, so $k=ap^j$ with $p\nmid a$. Then

$$\frac{q-k}k=\frac{p^n-ap^j}{ap^j}=\frac{(p^{n-j}-a)p^j}{ap^j}\;,$$

and $p\nmid p^{n-j}-a$, since $j<n$.

-
I'm not sure I immediately see why in the product the numerator and denominator has the same number of p-factors. –  Gadi A Jul 14 '11 at 18:50
This is similar to a part of a proof of the first Sylow theorem: en.wikipedia.org/wiki/… –  Ofir Jul 15 '11 at 19:44

This (and some generalizations) follow nicely from Lucas' Theorem, which is not too hard to prove.

To find $\binom{m}{n}$ modulo $p$, you just need to expand $m$ and $n$ in base $p$ digits as $m=m_0 + m_1p + \ldots +m_dp^d$ and $n=n_0+n_1p+\ldots + n_c p^c$. Then $$\binom{m}{n} \equiv \prod_i \binom{m_i}{n_i} \pmod{p}.$$

If $m=p^r$ and $1<n<p^r$, then $n_i \neq 0$ for some $i<r$. Then we have $\binom{m_i}{n_i} = \binom{0}{n_i} = 0$, so $\binom{m}{n} \equiv 0 \pmod{p}.$

EDIT: Here's a proof that $\binom{p^n}{i} \equiv 0 \pmod{p}$ for $0<i<p^n$, specializing the proof of Lucas' theorem given in Wikipedia.

We have a set $M$ of size $p^n$, and we want to count (mod $p$) the size $i$ subsets of $M$. The cyclic group $C_{p^n}$ of size $p^n$ acts on $M$, and it also acts on the set of all size $i$ subsets of $M$. Since $0<i<p^n$, no size $i$ subset is fixed by $C_{p^n}$; so the set of size $i$ subsets of $M$ is partitioned by $C_{p^n}$ into several nontrivial orbits. The size of each orbit must be divisible by $p$, so $\binom{p^n}{i} \equiv 0$ modulo $p$.

-
The shortest proof I know is by comparing the coefficient of $x^n$ in 2 equal polynomials (modulo $p$): $(1+x)^m$ and $\prod_{i}(1+x)^{m_{i}p^{i}} \equiv \prod_{i}(1+x^{p^i})^{m_i}$. This polynomial identity follows by repeated application of $(1+y)^p \equiv 1+y^p$, which in itself is equivalent to $\binom{p}{i} \equiv 0$ –  Ofir Jul 15 '11 at 19:40
@Ofir: There is an independent combinatorial proof given in the Wikipedia article: We have a set $M$ of size $m$ and want to count (mod $p$) the subsets of size $n$. We define a group $G$ acting on $M$ corresponding to the base $p$ digits of $m$: for each $i$, we have $m_i$ cycles of size $p^i$, all mutually disjoint. The group is the product over $i$ of $m_i$ copies of the cyclic group on $p^i$ elements. The group $G$ also acts on the set of all size $n$ subsets of $M$, cutting it into orbits. The nontrivial orbits must have size $p^j$; so to count mod $p$, we need only count fixed points. –  Jonas Kibelbek Jul 15 '11 at 20:51
But for a subset of $M$ to be fixed by $G$, it must be an entire $p^i$-cycle, or a union of several $p^i$-cycles. To get a size $n$ subset of $M$ fixed by $G$, we must used the base $p$ digits of $n$. That is, for each $i$, we choose $n_i$ of the $m_i$ $p^i$-cycles. –  Jonas Kibelbek Jul 15 '11 at 20:56

It is an immediate consequence of this elementary proof that binomial coefficients are integers. That proof algorithmically changes the bijection below between numerators and denominators

$$\rm {\:k\:\choose \:i\:}\ =\ \frac{k}{i}\ \frac{k-1}{i-1}\ \cdots \frac{k-i+1}{1}$$

so that the power of the prime $\rm\:p\;$ in every numerator is $\:\ge\:$ that of its denominator. But when $\rm\: i < k = p^n\:$ one of these inequalities must be strict. Namely, the fraction having numerator $\rm\:p^n\:$ has denominator $\rm\le i < p^n\:$ so its power of $\rm\:p\:$ is $\rm\: < n\:.\:$ Thus there are more factors of $\rm\:p\:$ in the numerator product than in the denominator product, so $\rm\:p\:$ divides their quotient $\rm\:\in \mathbb Z\:.$

-

Since $p$ is a prime, it's that $v_{p}(ab)=v_{p}(a)+v_{p}(b)$. So, $\displaystyle v_{p}(\binom{p^n}{i})=v_{p}(\frac{p^n}{i}\binom{p^n-1}{i-1})=v_{p}(\frac{p^n}{i})+v_{p}(\binom{p^n-1}{i-1})\geq v_{p}(\frac{p^n}{i})>0$. (any binomial coefficient $B$ is an integer, therefore $v_{p}(B)\geq0$)

-
Hello, welcome to Mathematics.SE and thank you for your answer! You may want to use \left and \right commands as explained here (point 6) to make things look nicer. You also may want to clarify what you use $v_p$ on $\Bbb Q$ (since $\frac{p^n}i$ is not necessarily an integer). You can edit your answer to implement these changes. –  Lord_Farin Jun 28 '13 at 8:27

Here's a slightly different proof from the one's presented above: We show that for a prime $p$ we can show that $p|\binom{p^k}{i}$ for $1\le i\le p^k-1$. Due to the fact that $\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor$ we have $$\sum_{j=1}^{k}\left(\left\lfloor\frac{i}{p^j}\right\rfloor+\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\le\sum_{j=1}^{k}\left\lfloor\frac{p^k}{p^j}\right\rfloor.$$ The LHS is the number of factors of $p$ in $i!(p^k-i)!$ and the RHS is the number of factors of $p$ in $p^k!$, by Legendre's formula. We have $$\left\lfloor\frac{i}{p^k}\right\rfloor=\left\lfloor\frac{p^k-i}{p^k}\right\rfloor = 0, \left\lfloor\frac{p^k}{p^k}\right\rfloor=1,$$ so the inequality is strict, so at least one factor of $p$ must divide $\binom{p^k}{i}$.

-