Binomial Residues (Putnam 1991)
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Let $p$ be an odd prime. Prove that $\sum_{j=0}^{p} \binom {p} {j}\binom {p+j} {j}\equiv 2^p+1\pmod {p^2}$
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Binomial Residues (Putnam 1991)
For $p=3$, prove it by computing both sides of the congruence. And for $p>3$, prove at first $\binom{p+j}j\equiv 1\pmod p$ for $p>j>0$. Since $p|\binom p j$, we derive, $\binom p j \binom{p+j}{j}\equiv \binom p j\pmod{p^2}$. Hence, \[\sum_{p\ge j\ge 0}\binom p j \binom{p+j}{j}\equiv 1+ \binom{2p}p+ \sum_{p-1\ge j\ge 1}\binom p j\equiv 1+2^p\pmod{p^2}\]
Where the last congruence follows from $\binom {2p}p\equiv 2\pmod{p^2}$(Wolstelholme) and $\sum \binom p i=2^p$.
Where the last congruence follows from $\binom {2p}p\equiv 2\pmod{p^2}$(Wolstelholme) and $\sum \binom p i=2^p$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
Re: Binomial Residues (Putnam 1991)
You don't have to use Wolstenholme here, think a bit.Phlembac Adib Hasan wrote:For $p=3$, prove it by computing both sides of the congruence. And for $p>3$, prove at first $\binom{p+j}j\equiv 1\pmod p$ for $p>j>0$. Since $p|\binom p j$, we derive, $\binom p j \binom{p+j}{j}\equiv \binom p j\pmod{p^2}$. Hence, \[\sum_{p\ge j\ge 0}\binom p j \binom{p+j}{j}\equiv 1+ \binom{2p}p+ \sum_{p-1\ge j\ge 1}\binom p j\equiv 1+2^p\pmod{p^2}\]
Where the last congruence follows from $\binom {2p}p\equiv 2\pmod{p^2}$(Wolstelholme)and $\sum \binom p i=2^p$.
One one thing is neutral in the universe, that is $0$.
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Binomial Residues (Putnam 1991)
I know. To be honest, I don't like invoking theorems for killing purposes, either. But that theorem was worth mentioning here because this result is direct consequence of a theorem $\binom{ap}{bp}\equiv \binom a b\pmod{p^3}$ which itself is derived from Wolstenholme. Also, in this forum, many beginners read and will read this post. And if they can learn a new cool theorem from here, I think it's ok anyway.
btw, Masum vai, please read this and revise your signature. http://www.matholympiad.org.bd/forum/vi ... f=9&t=3143
btw, Masum vai, please read this and revise your signature. http://www.matholympiad.org.bd/forum/vi ... f=9&t=3143
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
Re: Binomial Residues (Putnam 1991)
Ok. Thanks for notifying the issue
One one thing is neutral in the universe, that is $0$.