Let $n \geq 3$, show ${2n \choose n}$ is not divisible by $p$ for all primes $\frac{2n}{3} Note: This fact along with other facts about ${2n \choose n}$ are used in a proof of Bertrand's postulate.
Primes Not Dividing $\binom{2n}{n}$
4
$\begingroup$
elementary-number-theory
binomial-coefficients
-
1Any such prime appears exactly twice both in the numerator and the denominator of $\binom{2n}{n}= \frac{(2n)!}{(n!)^2}$. – 2012-08-14
1 Answers
7
I think that the idea is rather simple (not verifying Brian's hint...) :
We need to divide $(2n)!$ by $n!^2$ so let's write the primes of the decomposition of $(2n)!$ and $n!$.
Let's suppose that $\frac n2 is such a prime larger than $2$ then : $ \binom{2n}{n} = \frac{(2n)!}{(n!)^2}= \frac{ 2n\cdot (2n-1)\cdots(2p)\cdots (n)\cdots (p)\cdots 2\cdot 1} {(n)\cdots (p)\cdots 2\cdot 1\cdot (n)\cdots (p)\cdots 2\cdot 1} $ When $3p\le 2n$ we will have at least $3$ $p$'s at the top and the fraction will be divisible by $p$ else the two $p$ will cancel !