Binomial coefficient

**alexmahone** · August 19th 2011, 10:35 PM

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

**melese** · August 20th 2011, 01:35 PM

Originally Posted by alexmahone

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

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

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

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

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

Thread: Binomial coefficient

LinkBack

Thread Tools

Display

Binomial coefficient

Re: Binomial coefficient

Similar Math Help Forum Discussions

Binomial Coefficient

binomial coefficient.

Binomial Coefficient

Binomial Theorem or Binomial Coefficient

Binomial Coefficient

Search Tags