24
$\begingroup$

It is quite easy to show that for every prime $p$ and $0

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

39

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]

  • 2
    Beautiful pic! If it's not a secret, could you share the *Mathematica* code you used?2011-12-07
  • 0
    @J.M. Thank you J.M.! With pleasure, I will add it in right away.2011-12-07
  • 4
    @J.M. Code should never be secret, unless it's a secret code.2011-12-07
  • 1
    You have it backwards; thank **you** for the answer, the picture, and the code.2011-12-07
  • 0
    Your picture reminds me of the [Sierpinski triangle](http://en.wikipedia.org/wiki/Pascal%27s_triangle#Overall_patterns_and_properties).2011-12-07
  • 1
    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. :)2011-12-07
  • 0
    And @J.M., you are very welcome. :)2011-12-07
  • 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$.

  • 0
    Can you elaborate what you mean by "repeat"?2011-07-14
  • 0
    Ok, I got it, your solution is quite elegant. Thanks!2011-07-14
  • 1
    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.2011-07-14
  • 1
    @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$.2011-07-15
  • 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

  • 0
    I'm not sure I immediately see why in the product the numerator and denominator has the same number of p-factors.2011-07-14
  • 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


EDIT: Here's a proof that $\binom{p^n}{i} \equiv 0 \pmod{p}$ for $0

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

  • 1
    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$2011-07-15
  • 0
    @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.2011-07-15
  • 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

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

0

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

Let $0

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!