Binoial congruence(mod p)

For discussing Olympiad Level Number Theory problems
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
Binoial congruence(mod p)

Unread post by mutasimmim » Sat Sep 27, 2014 11:17 pm

Prove that for any odd prime $p$ , $\binom {2p}{p}\equiv 2\pmod {p^3}$

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Binoial congruence(mod p)

Unread post by SANZEED » Mon Sep 29, 2014 5:49 pm

I think there is a typo, because your statement is false for $p=3$. May be the correct statement is $2p\choose p$ $\equiv 2(mod p^{2})\forall p=$ prime. I have a proof for this.

Let us choose a set of $p$ boys and girls from a set of $p$ boys and $p$ girls. Firstly, this can be done in $2p\choose p$ ways. Now count it in another way. If we choose $i$ boys out of $p$ boys, then we have to $(p-i)$ girls out of $p$ girls. This can be done in $p\choose i$ $\times$ $p\choose p-i$ $=$ $p\choose i$ $^2$ ways. So the total number of ways to choose a set of $p$ boys and girls is $\sum_{i=0}^{p}$ $p\choose i$ $^2$. Thus,
$2p\choose p$ $=$ $\sum_{i=0}^{p}$ $p\choose i$ $^2$. Now it is a well-known identity that $p|$ $p\choose i$ if and only if $(p,i)=1$. Thus $p|$ $p\choose i$ $\forall i=1,2,3,...,p-1$. So, $p^{2}|$ $p\choose i$ $^{2}$ $ \forall i=1,2,3,...,p-1$
So, $2p\choose p$ $=$ $\sum_{i=0}^{p}$ $p\choose i$ $^2$ $\equiv$ $p\choose 0$ $+$ $p\choose p$ $\equiv 2(mod p^{2})$.

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Binoial congruence(mod p)

Unread post by Phlembac Adib Hasan » Mon Sep 29, 2014 7:25 pm

@Sanzeed, there IS a typo. But It's not about the power of $p$. This problem is true for $p>3$ and simply derives from a variation of the Wolstenholme's theorem. \[\binom{ap}{bp}\equiv \binom{a}{b}\pmod{p^3}\]
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply