elementary number theory - Prime dividing the binomial coefficients

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

Answer

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]