# Binomial coefficient

• Aug 19th 2011, 10:35 PM
alexmahone
Binomial coefficient
Let $\displaystyle p\geq3$ be a prime number, and let m and $\displaystyle k<p^m$ be positive integers. Show that $\displaystyle \dbinom{p^m}{k}$ is divisible by p.
• Aug 20th 2011, 01:35 PM
melese
Re: Binomial coefficient
Quote:

Originally Posted by alexmahone
Let $\displaystyle p\geq3$ be a prime number, and let m and $\displaystyle k<p^m$ be positive integers. Show that $\displaystyle \dbinom{p^m}{k}$ is divisible by p.

We have the simple identity $\displaystyle \binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot\frac{p^m}{k}$ for $\displaystyle 0<k$. Hence, (a)$\displaystyle k\cdot\binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot p^m$.

Let $\displaystyle p^j$ be the largest power of $\displaystyle p$ that divides $\displaystyle k$. So $\displaystyle \frac{k}{p^j}\cdot\binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot p^{m-j}$, by (a).

From $\displaystyle p^j\leq k<p^m$ it follows that $\displaystyle m-j>0$ and so $\displaystyle p$ divides $\displaystyle \frac{k}{p^j}\cdot\binom{p^m}{k}$, where $\displaystyle p$ does not divide $\displaystyle \frac{k}{p^j}$. Euclid's Lemma implies then that $\displaystyle p$ must divide $\displaystyle \binom{p^m}{k}$.

By the way, the argument works for $\displaystyle p=2$ also.