Binomial Coefficient of a Prime Power

[MissMoneypenny]

Homework Statement

Let p be a prime, k be positive integer, and m ∈ {1, 2, 3, ..., p^k-1}. Without using Lucas' theorem, prove that p divides \binom{p^k}{m}.

Homework Equations

The definition of the binomial coefficients: \binom{a}{b} = \frac{a!}{b! (a-b)!}

The Attempt at a Solution

I've managed to prove the statement when k=1 by arguing that p must divide p! but cannot possible divide m!(p-m)!. I figure I should be able to use a similar counting argument for this proof, likely by counting the number of factors of p that appear in the numerator and in the denominator of \binom{p^k}{m}. It looks to me as though the number of factors of p in p^k ! is \sum_{i=1}^{k} p^{k-i}. However, I'm having applying this to the problem. If anyone could give some advice on how to do so, or perhaps nudge me in the direction of a different proof it would be much appreciated.

Thanks!

 

[mfb]

That counting argument should work. You can can find a similar formula for m! and (p^k-m)! and try to evaluate the difference.

Or directly consider the fraction as
$$\frac{p^k \cdot (p^k-1) \cdot \dots}{m! \cdot (m-1)! \cdot \dots}$$ and try to find matching factors there. Hmm... induction over m?

 

[MissMoneypenny]

Thanks for the help. I followed your advice and worked out similar formulas for m! and for (p^k-m)!, and managed to prove the result by bounding the difference using geometric series. I appreciate your comment, it gave me the little push in the right direction that I needed.