A simple binomial identity

Question

Is there a simple way of showing that a prime $p$ must divide the binomial coefficient $p^n\choose{k}$ for all $n\geq 1$ and $1\leq k\leq p^n-1$?

Answer 1

$$\binom{p^n}{k} = \frac{p^n (p^n -1) ... (p^n -k+1)}{k!}= \frac{p^n}{k} \cdot \frac{ (p^n -1) ... (p^n -k+1) }{(k-1)!} = \frac{p^n}{k} \cdot \underbrace{\binom{p^n -1}{k-1}}_{\in \mathbb{Z}} $$

$p \Big| p^n$ and because $k<p^n$ we get that $$p \Big| \binom{p^n}{k}$$ Q.E.D

Answer 2

In this answer is is shown that the number of factors of $p$ that divide $\binom{n}{k}$ is $$ \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$.

Since $\sigma_p\!\left(p^n\right)=1$ and $k,p^n-k\ne0$, we have that $\sigma_p(k),\sigma_p\!\left(p^n-k\right)\ge1$. Thus, $$ \frac{\sigma(k)+\sigma\!\left(p^n-k\right)-\sigma\!\left(p^n\right)}{p-1}\gt0\tag{2} $$ Therefore, the number of factors of $p$ that divide $\binom{p^n}{k}$ is greater than $0$.

Answer 3

Just a quick remark after the fact: If you accept that $$ (a +b )^{p} \equiv a^p +b^p\pmod p ,$$ for $a$ and $b$ indeterminants, then $$(a+b)^{p^n} = \left(\ (a + b )^p\ \right)^{p^{n-1}}\equiv \left(\ a^p + b^p\ \right)^{p^{n-1}}\equiv a^{p^n}+ b^{p^n}\pmod p,$$ which also gives the result.

Answer 4

$$\begin{align*}\binom{p^n}{k} = \frac{(p^n)!}{k! (n-k)!} &= \frac{(p^n)(p^n-1)(p^n-2)(p^n-3)\cdots (p^n-(k-1))}{1\cdot 2\cdot 3 \cdots (k-1)k} \\ &= \frac{p^n}{k}\cdot \frac{p^n-1}{1} \cdot \frac{p^n-2}{2}\cdots \frac{p^n-(k-1)}{k-1} \\ &= \frac{p^n}{k} \cdot \prod_{i=1}^{k-1} \frac{p^n-i}{i}.\end{align*}$$ (Note that these smaller fractions are not necessarily integers.)

We are trying to show that after all cancellations of prime factors, there remains at least one factor of $p$ in the numerator of this large fraction.

Consider the fractions of the form $\frac{p^n-i}{i}$. Now $p^n-i$ is divisible by $p^j$ if and only if $i$ is divisible by $p^j$, for all $1\leq j\leq n$. So in each fraction $\frac{p^n-i}{i}$, all the $p$'s in the numerator and denominator cancel perfectly. So in the entire fraction, the only remaining $p$'s in the numerator are those in $p^n$, and the only remaining $p$'s in the denominator (if any) are factors of $k$. But $k<p^n$, so $k$ can have at most $n-1$ factors of $p$, leaving at least one left over in the numerator.