Prove that a binomial coefficient is not divisible by p.

freemind

Prove that a binomial coefficient is not divisible by p.

**Posted:** Sun Mar 30, 2008 3:41 pm

_________________
The fate of equilibrium is to end the eternity...

ZetaX

Trivial by Lucas theorem.
Or write the binomial coefficient out and look how often each term is divisible by $p$ .
You even have (for $p > 3$ ) the much stronger property $\binom{n \cdot p^k}{p^k} \equiv n \mod p^{k + 3}$ for arbitrary $n$ .

**Posted:** Sun Mar 30, 2008 3:49 pm

_________________
The one and only place to get next year's IMO problems already now!

Vrajitoarea Andrei

#3

I see another approach.
Let us denote $v_{p}(n)$ the exponent of $p$ in the prime representation of the natural number $n$ .It is trvial the fact that for $a,b \in \mathbb{N}$ we have $v_{p}(ab)=v_{p}(a)+v_{p}(b)$ and also $v_{p}(\frac{a}{b})=v_{p}(a)-v_{p}(b)$ .It is also known the fact that : $v_{p}(n!)=\sum_{k=1}^{\infty} \left[ \frac{n}{p^{k}} \right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^{2}}\right]+...$
In order to prove $\dbinom {np^{k}}{p^{k}}$ and $p$ are coprime , we must show that $v_{p}(\dbinom{np^{k}}{p^{k}})=0$ .
But this is true because: $v_{p}(\dbinom{np^{k}}{p^{k}})=v_{p}(\frac{(np^{k})!}{p^{k}!(np^{k}-p^{k})!})=v_{p}((np^{k})!)-\left(v_{p}(p^{k}!)+v_{p}((np^{...$
$=\sum_{i=1}^{\infty} \left[\frac{np^{k}}{p^{i}}\right]- \sum_{i=1}^{\infty} \left(\left[\frac{p^{k}}{p^{i}}\right]+\left[\fra...$
$=n(p^{k-1}+p^{k-2}+...+p+1)-(p^{k-1}+p^{k-2}+...+p+1)-(n-1)(p^{k-1}+p^{k-2}+...+p+1)+\sum_{i=1}^{\infty} \left[\frac{n}{p^{i}...$
Because $\gcd(n,p)=1$ it follows that $\sum_{i=1}^{\infty} \left[\frac{n}{p^{i}}\right]=\sum_{i=1}^{\infty} \left[\frac{n-1}{p^{i}}\right]$ so $v_{p}(\dbinom{np^{k}}{p^{k}})=0$ meaning $\gcd(p,\dbinom{np^{k}}{p^{k}})=1$ .

**Posted:** Sat Jun 21, 2008 6:06 pm

Rust

#4

**Posted:** Sat Jun 21, 2008 7:54 pm

nguyenvuthanhha

#5

A good solution , Vrajitoarea Andrei Smile

**Posted:** Sun May 24, 2009 11:10 am

_________________
Love the simplicity