26
$\begingroup$

It is quite easy to show that for every prime $p$ and $0 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$.

  • 1
    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.2011-07-14

8 Answers 8

40

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.

the triangle

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]

  • 0
    @BrunoJoyal I stumbled across this (nice) answer searching for something similar. Could you please explain what you are doing in the last part of the proof, between "Therefore," and "Hence we have...", especially the summation simplification?2015-04-10
17

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

  • 1
    @Gadi, if you're worried about cancellation, you can work with the field Z/p(x,y), where x and y are transcendentals.2011-07-16
9

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

  • 1
    This is similar to a part of a proof of the first Sylow theorem: http://en.wikipedia.org/wiki/Sylow_theorems#Proof_of_the_Sylow_theorems2011-07-15
6

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_d p^d$ (leading zeroes are allowed). Then $ \binom{m}{n} \equiv \prod_i \binom{m_i}{n_i} \pmod{p}.$

If $m=p^r$ and $0, then $n_i \neq 0$ for some $i. 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, 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, 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$.

  • 0
    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.2011-07-15
2

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\:.$

  • 0
    If $m \ge n$, it doesn't necessary mean that $v_p(m) \ge v_p(n)$. Example: $v_2(5)=0$, $v_2(4)=2$.2017-11-14
2

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$)

  • 0
    Hello, welcome to Mathematics.SE and thank you for your answer! You may want to use `\left` and `\right` commands as explained [here](http://meta.math.stackexchange.com/q/5020/43351) (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.2013-06-28
1

This is a simplification of proof suggested by user84232. (Probably the simplest proof, I see here).

Let $0. Then $i=p^kj$, where $0\le k, while $p$ and $j$ are co-prime.

Therefore

$ \binom{p^n}{i}=\frac{p^n}{i}\;\binom{p^n-1}{i-1}= \frac{p^{n-k}}{j}\;\binom{p^n-1}{i-1} $

which can be rewritten as

$ j\;\binom{p^n}{i}=p^{n-k}\;\binom{p^n-1}{i-1} $

Since $j$ and $p^{n-k}$ are co-prime, $\binom{p^n}{i}$ must be divisible by $p^{n-k}$, so (because of $n>k$) divisible by $p$. That's it!

0

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