Iran-NMO-2010-1

For discussing Olympiad Level Number Theory problems
User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.
Iran-NMO-2010-1

Unread post by Tahmid Hasan » Fri Dec 28, 2012 7:47 pm

Let $a,b$ be two positive integers and $a>b$.We know that $\gcd (a-b,ab+1)=1$ and $\gcd (a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square.
বড় ভালবাসি তোমায়,মা

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Iran-NMO-2010-1

Unread post by SANZEED » Sat Dec 29, 2012 9:34 pm

It is easy to show that $(a-b)^2+(ab+1)^2=(a^2+1)(b^2+1)$. If we can prove that $(a^2+1,b^2+1)=1$ then we're done.
Let $d=(a^2+1,b^2+1)$. Assume to the contrary that $d\neq 1$. Now $d|(a^2+1)-(b^2+1)=(a+b)(a-b)$. As $d>1$, let $p$ be a prime divisor of $d$. Now $p$ divides either $(a+b)$ or $(a-b)$. If $p|(a-b)$ then since $p|(a^2+1)(b^2+1)\Rightarrow p|(ab+1)\Rightarrow p|(a-b,ab+1)=1$, a contradiction. Similar contradiction can be showed if we assume that $p|(a+b)$. So we were wrong assuming that $d\neq 1$. So $d=1$ and that implies that both $a^2+1$ and $b^2+1$ are perfect squares which is impossible. :|
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
Nadim Ul Abrar
Posts:244
Joined:Sat May 07, 2011 12:36 pm
Location:B.A.R.D , kotbari , Comilla

Re: Iran-NMO-2010-1

Unread post by Nadim Ul Abrar » Sun Dec 30, 2012 10:45 am

পীথাগোরিয়ান ট্রিপল এর ক্ষেত্রে , Primitive ট্রিপল থাকে একটা । বাট ,

$(a-b)^2+(ab+1)^2=(a+b)^2+(ab-1)^2$
$\frac{1}{0}$

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: Iran-NMO-2010-1

Unread post by Tahmid Hasan » Sun Dec 30, 2012 12:05 pm

Nadim Ul Abrar wrote:পীথাগোরিয়ান ট্রিপল এর ক্ষেত্রে , Primitive ট্রিপল থাকে একটা । বাট ,

$(a-b)^2+(ab+1)^2=(a+b)^2+(ab-1)^2$
নাদিম ভাই দেখি আমার মতই ওয়ান লাইনার মেরে দিলেন। আওপ্সে এই প্রব্লেমটাতে মাসুম ভাইও একই সমাধান দিছে :)
বড় ভালবাসি তোমায়,মা

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

Re: Iran-NMO-2010-1

Unread post by *Mahi* » Sun Dec 30, 2012 12:30 pm

Nadim Ul Abrar wrote:পীথাগোরিয়ান ট্রিপল এর ক্ষেত্রে , Primitive ট্রিপল থাকে একটা ।
এইটার প্রুফ দিতে হবে না? :/
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
Nadim Ul Abrar
Posts:244
Joined:Sat May 07, 2011 12:36 pm
Location:B.A.R.D , kotbari , Comilla

Re: Iran-NMO-2010-1

Unread post by Nadim Ul Abrar » Sun Dec 30, 2012 12:39 pm

আচ্ছা এইসব জিনিস কি প্রফ কইরা ইউস করা লাগে ??
$\frac{1}{0}$

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

Re: Iran-NMO-2010-1

Unread post by *Mahi* » Sun Dec 30, 2012 12:45 pm

Nadim Ul Abrar wrote:আচ্ছা এইসব জিনিস কি প্রফ কইরা ইউস করা লাগে ??
কনটেস্টে অবশ্যই দেয়া উচিত, আমার মনে হয় না এইটা খুব বেশি ট্রিভিয়াল কিছু।
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
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Iran-NMO-2010-1

Unread post by Phlembac Adib Hasan » Sun Dec 30, 2012 1:17 pm

@ Nadim ভাই, পিথাগোরিয়ান ট্রিপল দিয়ে আমিও করেছি তবে অন্যভাবে। মানে $a-b=2mn, ab+1=m^2-n^2$ এভাবে আরকি। কিন্তু আপনার এক লাইন থেকে সল্যুশন ঠিক বুঝলাম না। এরকমটা তো হতেই পারে, যেমন-
$(19^2-4^2)^2+(2\times 19\times 4)^2=377^2=(16^2-11^2)^2+(2\times 16\times 11)^2$
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Nadim Ul Abrar
Posts:244
Joined:Sat May 07, 2011 12:36 pm
Location:B.A.R.D , kotbari , Comilla

Re: Iran-NMO-2010-1

Unread post by Nadim Ul Abrar » Sun Dec 30, 2012 3:29 pm

আওপ্স , আমি তাইলে ভুল ছিলাম :) । @ আদিব ।
(মাহি , সরি :P )
$\frac{1}{0}$

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

Re: Iran-NMO-2010-1

Unread post by Phlembac Adib Hasan » Sun Dec 30, 2012 6:49 pm

My solution:
From the identity of Nadim vai, we can find two different Pythagorean triples.
Case 1: $a-b$ even
So $a-b=2mn;ab+1=m^2-n^2$
Since $a-b$ and $a+b$ have same parity, $a+b=2xy;ab-1=x^2-y^2$
and $m^2+n^2=x^2+y^2\Longrightarrow m^2-x^2=y^2-n^2$

Therefore, $m^2-n^2=x^2-y^2+2\Longrightarrow 2(m^2-x^2)=2\Longrightarrow m^2-x^2=1$
which is strictly impossible.
Case 2: $a-b$ odd
$a-b=m^2-n^2;ab+1=2mn$
$a+b=x^2-y^2;ab-1=2xy$
and $m^2+n^2=x^2+y^2$

We get $2mn-2xy=2\Longrightarrow mn-xy=1$
Therefore, $(m+n)^2-(x+y)^2=2$
still impossible like the previous and we're done.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply