# Binomial Coefficient of a Prime Power

Tags:
1. Nov 23, 2014

### MissMoneypenny

1. The problem statement, all variables and given/known data
Let p be a prime, k be positive integer, and m ∈ {1, 2, 3, ..., pk-1}. Without using Lucas' theorem, prove that p divides $\binom{p^k}{m}$.
2. Relevant equations
The definition of the binomial coefficients: $\binom{a}{b} = \frac{a!}{b! (a-b)!}$

3. 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!

Last edited: Nov 23, 2014
2. Nov 24, 2014

### Staff: Mentor

That counting argument should work. You can can find a similar formula for m! and (pk-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?

3. Nov 24, 2014

### MissMoneypenny

Thanks for the help. I followed your advice and worked out similar formulas for m! and for (pk-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.