IMO Shortlist 1995 N1

For discussing Olympiad Level Number Theory problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
IMO Shortlist 1995 N1

Unread post by Phlembac Adib Hasan » Thu Mar 21, 2013 10:23 am

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!

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Apmo/IMOsl problem, forgot the year

Unread post by *Mahi* » Thu Mar 21, 2013 10:51 am

ক্যাম্পেই করসিলি না এইটা?
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
FahimFerdous
Posts:176
Joined:Thu Dec 09, 2010 12:50 am
Location:Mymensingh, Bangladesh

Re: Apmo/IMOsl problem, forgot the year

Unread post by FahimFerdous » Thu Mar 21, 2013 1:51 pm

ISL 1995 N1
Your hot head might dominate your good heart!

User avatar
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

Unread post by Phlembac Adib Hasan » Thu Mar 21, 2013 4:59 pm

*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.

Post Reply