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$.
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]
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$.
$$\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$.
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<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$.
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$)
\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.
$\endgroup$
Commented
Jun 28, 2013 at 8:27
This is a simplification of proof suggested by user84232. (Probably the simplest proof, I see here).
Let $0<i<p^n$. Then $i=p^kj$, where $0\le k<n$, 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!
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\:.$
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}$.
