# A simple binomial identity

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$?

-

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.

-
Indeed, this is even easier! – ougoah Mar 30 at 7:08
I don't know about that! I liked Yonatan's answer too. – peter a g Mar 30 at 11:32

$$\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

-
I must be missing something simple: why does $p\mid p^n$, from the previous line? – Clement C. Mar 29 at 14:08
This is immediate. – Yonatan Mar 29 at 14:17
@ClementC. The highest power of $p$ that can divide $k$ is $p^{n-1}$. All other factors of $k$ divide $\binom{p^n -1}{k-1}$. This leaves at least one factor of $p$ remaining. – Paul Sinclair Mar 29 at 17:44
@PaulSinclair OK. (This may be splitting hair, but the point of my comments is that adding that to the answer may have been a good thing.) – Clement C. Mar 29 at 17:45
@ClementC. - agreed. This is a little much to have been left unsaid. – Paul Sinclair Mar 29 at 17:46

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$.

-
Nice. To make it less depending on the link you could add a definition of $\sigma_p$. – drhab Mar 29 at 12:55
@drhab: good idea. Thanks! – robjohn Mar 29 at 12:59

\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.

-
+1 nice demonstration. – Paul Sinclair Mar 29 at 17:49