Binoial congruence(mod p)
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Prove that for any odd prime $p$ , $\binom {2p}{p}\equiv 2\pmod {p^3}$
Re: Binoial congruence(mod p)
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})$.
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})$.
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Binoial congruence(mod p)
@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