Proof that $ p $ | ${ p^n \choose k } $ for any prime $p$ and $ k < p^n$

I know how to prove the fact that $ p$ | ${ p \choose k } $ (when writing it as a fraction, $p$ cannot be divided by any of the $1\times2\times...\times k$ or $1\times2\times...\times(p-k)$ because $p$ is prime).

When I try to apply the same rationale for $ p$ | ${ p^n \choose k } $ I get stumped because $p^n$ is in fact divisible by one of the $k! = 1\times2\times...\times k$, where $0 < k < p^n$.

If we take the example of $2^3$ and $k = 7$, we can easily see that $k! = 1 \times 2 \times ... \times 6 \times 7$, and $2$ clearly divides $2^3$.

How else can I approach this?

Solution 1:

The following identity holds:

$$\binom{p^n}{k}=\frac{p^n}{k} \binom{p^n-1}{k-1}.$$

Hence

$$k\binom{p^n}{k}=p^n\binom{p^n-1}{k-1}$$

which implies that $$p^n\mid k\binom{p^n}{k}.$$

• If $p$ and $k$ are coprime, then $p^n \mid \binom{p^n}{k}$, with $p \mid p^n$. This completes the proof.

• If they're not, then there exists a maximal $\alpha <n$ and $q \in \mathbb N$ such that $k=p^\alpha q$ (note that $q$ and $p$ are coprime).

We have that $$q \binom{p^n}{k}=p^{n-\alpha} \binom{p^n-1}{k-1}$$ and $n-\alpha \geq 1$

Thus $$p\mid p^{n-\alpha}$$ and $$p^{n-\alpha}\mid \binom{p^n}{k}.$$

Finally $$p\mid \binom{p^n}{k}.$$