Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$?
$${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = \frac{p^mn(p^mn-1)(p^mn-2)\cdots(p^mn-p^m+1)}{p^m(p^m-1)(p^m-2)\cdots(p^m-p^m+1)}$$
I can see $p^m$ cancel out in the first term, but why is this not divisible by $p$?
On
Suppose $p\mid(p^mn-k)$.
Then we have $px=p^mn-k$ or $p^mn-px=k$ where you can find $p(p^{m-1}n-x)=k$ (since $p\nmid n$). Therefore $p\mid(p^m-k)$ so we can cancel prime divisors.
On
This question here: A problem regarding the proof of ${p^nk\choose p^n}\equiv k\mod p$, where $p\nmid k$. shows the following: $$ {p^m n \choose p^m} \equiv n \ \mathrm{(mod\ p)}$$
Your question follows from this; I hope that helped.
Edit (In response to the below comment): $$(1+X)^{mp^a} \equiv (1+X^{p^a})^m\ \mathrm{(mod\ p)}$$ Which is the same as saying $$\sum_{r=0}^{r=mp^a}{\left(X^{r}{mp^a \choose r}\right)} \equiv \sum_{r=0}^{r=m}{\left(X^{rp^a}{m \choose r}\right)}\ \mathrm{(mod\ p)}$$
The coefficents of $X^{p^a}$ on each side are $mp^a \choose p^a$ (When $r=p^a$) and $m \choose 1$ (When $r=1$) respectively, but these are the congruent modulo $p$, thus $${mp^a \choose p^a} \equiv m \mathrm{(mod\ p)}$$
Writing $$ \binom{p^mn}{p^m} =\frac{p^mn}{p^m}\times\frac{p^mn-1}{p^m-1}\times\cdots\times\frac{p^m(n-1)+1}1 $$ the factors $p$ in all individual fractions cancel out, so that none are left either in numerator or denominator. The product of all those rational numbers is of course an integer, that $p$ does not divide.
In fact this is just a very special case of Lucas' theorem, which for a binomial coefficient with lower index a power of$~p$ says that $\binom{p^mn}{p^m}\equiv n\pmod p$ for any $n$. Specialising the combinatorial proof at the link gives the following. Partition a set $S$ of size $p^mn$ greedily into a disjoint union of parts each of size some power of$~p$, taken as large as possible. Now let the cyclic group of order the largest $p$-power present act on $S$, by having its generator rotate each of the parts one unit forward. This acts on subsets of $S$ as well. Counting the number of $p^m$-element subsets modulo$~p$, we can ignore all those whose orbit has size divisible by$~p$; given the order of the group acting, these are all subsets, except those completely invariant under the action. But the smallest parts in our partition are of size $p^m$, and only the $p^n$-subsets precisely equal to one of those parts will be invariant under the action. There are $n\bmod p$ such parts, which gives the stated congruence modulo$~p$.