Binomial Residues (Putnam 1991)

For discussing Olympiad Level Number Theory problems
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
Binomial Residues (Putnam 1991)

Unread post by mutasimmim » Wed Oct 08, 2014 10:11 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}$

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

Re: Binomial Residues (Putnam 1991)

Unread post by Phlembac Adib Hasan » Sat Oct 11, 2014 10:04 am

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$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Binomial Residues (Putnam 1991)

Unread post by Masum » Sat Oct 11, 2014 10:49 pm

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$.
You don't have to use Wolstenholme here, think a bit.
One one thing is neutral in the universe, that is $0$.

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

Re: Binomial Residues (Putnam 1991)

Unread post by Phlembac Adib Hasan » Sun Oct 12, 2014 12:01 am

I know. :D 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
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Binomial Residues (Putnam 1991)

Unread post by Masum » Tue Oct 14, 2014 2:20 am

Ok. Thanks for notifying the issue
One one thing is neutral in the universe, that is $0$.

Post Reply