Suppose, $p$ is a prime. Show that, all the numbers in the $p^{th}$ row of the Pascal's Triangle (except $\binom{p}{0}$ and $\binom{p}{p}$) are divisible by $p$, i.e,
\[\displaystyle p\mid \binom{p}{k}\]
\[\displaystyle\forall 0<k<p\]
Factors of Binomials
Last edited by sowmitra on Thu Aug 16, 2012 5:00 pm, edited 1 time in total.
Re: Factors of Binomials
Lemma:
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: Factors of Binomials
$\binom{p}{k}=\frac{p!}{(p-k)!k!}$,$(p-k)!k!$ is coprime with $P \forall 0<k<p$ and $\binom{p}{k}$ is an integer,so we are done.sowmitra wrote:Suppose, $p$ is a prime. Show that, all the numbers in the $p^{th}$ row of the Pascal's Triangle (except $\binom{p}{0}$ and $\binom{p}{p}$) are divisible by $p$, i.e,
\[\displaystyle p\mid \binom{p}{k}\]
\[\displaystyle\forall 0<k<p\]
বড় ভালবাসি তোমায়,মা
Re: Factors of Binomials
@Tahmid: Quite a nice and easy solution. It seems I have overlooked it.
But, I have learnt a technique which makes good use of the lemma:
We have, $\displaystyle\binom{p}{k}=\frac{p}{k}\binom{p-1}{k-1}$
Therefore,$\displaystyle k\binom{p}{k}=p\binom{p-1}{k-1}$
Now, both sides of the identity are integers.So,
$\displaystyle p\mid k\binom{p}{k}$
Since, $k<p$ and $p$ is a prime, so, $(p,k)=1$
Then, we can say, $\displaystyle p\mid\binom{p}{k}$.
But, I have learnt a technique which makes good use of the lemma:
We have, $\displaystyle\binom{p}{k}=\frac{p}{k}\binom{p-1}{k-1}$
Therefore,$\displaystyle k\binom{p}{k}=p\binom{p-1}{k-1}$
Now, both sides of the identity are integers.So,
$\displaystyle p\mid k\binom{p}{k}$
Since, $k<p$ and $p$ is a prime, so, $(p,k)=1$
Then, we can say, $\displaystyle p\mid\binom{p}{k}$.
Re: Factors of Binomials
And here is a proof of the lemma. It's quite straightforward, actually :
We have,
$\displaystyle\binom{n}{r}=\frac{n!}{(n-r)!r!}=\frac{n.(n-1)!}{r.(n-r)!(r-1)!}=\frac{n}{r}.\frac{(n-1)!}{((n-1)-(r-1))!(r-1)!}=\frac{n}{r}\binom{n-1}{r-1}$
We have,
$\displaystyle\binom{n}{r}=\frac{n!}{(n-r)!r!}=\frac{n.(n-1)!}{r.(n-r)!(r-1)!}=\frac{n}{r}.\frac{(n-1)!}{((n-1)-(r-1))!(r-1)!}=\frac{n}{r}\binom{n-1}{r-1}$