Prove that for every positive integer $n$, there exist infinitely many positive integers $a,b$ such that $a\cdot 2^n-b^2=7$.
I solved it yesterday. It appeared interesting to me, so guys, have a look!
IMO Shortlist 1995 N1
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Apmo/IMOsl problem, forgot the year
ক্যাম্পেই করসিলি না এইটা?
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- FahimFerdous
- Posts:176
- Joined:Thu Dec 09, 2010 12:50 am
- Location:Mymensingh, Bangladesh
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Apmo/IMOsl problem, forgot the year
ক্যাম্পে তো আবালত্বপূর্ণ থিয়োরি দিয়া করসিলাম। এখন পিয়োর কন্সট্রাক্টিভ উপায়ে করসি।*Mahi* wrote:ক্যাম্পেই করসিলি না এইটা?
My Proof:
It is enough to show that hte modular equation $x^2\equiv -7\pmod {2^n}$ is solvable for every positive integer $n$.
We'll proceed by induction on $n$. The base case is true because $3^2\equiv -7\pmod{2^4}$.
So assume that this is true for some $n=k\ge 4$. i.e, $\exists d:\; d^2\equiv -7\pmod {2^k}$. Notice that $d^2\equiv -7$ or $2^k-7\pmod {2^{k+1}}$. If the first one occurs, we are done. So assume $d^2\equiv 2^k-7\pmod {2^{k+1}}\Longrightarrow d^2+7-2^k=2^{k+1}m$ for some integer $m$. So $d^2+7=2^k(2m+1)\Longleftrightarrow d^2+7+2^k(d+2^{k-2})=2^k(2m+(1+d)+2^{k-2})......(1)$
Notice that $d$ is odd. So $2m+1+d+2^{k-2}$ is divisible by $2$.
Hence from $(1)$, $7+(d+2^{k-1})^2=2^{k+1}r$ for some integer $r$. So done.