IMO Shortlist 2012 N1

For discussing Olympiad Level Number Theory problems
User avatar
Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

IMO Shortlist 2012 N1

Unread post by Thanic Nur Samin » Sat Aug 06, 2016 8:26 pm

We call a set $A$ of integers admissible if $x,y\in A$(not necessarily distinct), then $x^2+kxy+y^2\in A$ for every integer $k$.

Determine all pairs of nonzero integers $m,n$ for which if $m,n\in A$, then $A=\mathbb{Z}$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

Re: IMO Shortlist 2012 N1

Unread post by Thanic Nur Samin » Sat Aug 06, 2016 8:28 pm

Hint:
Use Bézout's identity to show $1\in A$ for coprime $m,n$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: IMO Shortlist 2012 N1

Unread post by nahin munkar » Sun Aug 07, 2016 12:00 am

OK. I have approached it like this.
Let, $d= gcd(m,n).$ If, $d > 1$, if $d|x$ & $ d|y $ then $d|x^2+kxy+y^2 $ for all k.So,though the multiple of d satisfies condition, but $A \ne \mathbb{Z}$. here it is easy to see, $ d=1$ .
Now,We let,the set $A$ is admissible containing m,n.So,if $ x^2 \in A$ , then,$ kx^2 \in A$ (calculating from condition). if $ d=1. gcd(m^2,n^2)=1$ . According to hint ,we get $ am^2+bn^2=1$ by bezout's theorem. We get here $(am^2+bn^2)^2=1 \in A...(*)$, where k =2. & also $am^2 \in A, bn^2\in A.$ From (*), $ 1 \in A $ ; As, all multiples of $ m^2 \in A, so, k*1^2=k \in A.$ For this, all integers $ \in A.$ $ SO, A=\mathbb{Z} . $....... :D
Last edited by nahin munkar on Sun Aug 07, 2016 7:21 pm, edited 1 time in total.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: IMO Shortlist 2012 N1

Unread post by asif e elahi » Sun Aug 07, 2016 10:19 am

nahin munkar wrote:OK. I have approached it like this.
Let, $d= gcd(m,n).$ If, $d > 1$, if $d|x$ & $ d|y $ then $d|x^2+kxy+y^2 $ for all k.So,though the multiple of d satisfies condition, but $A \ne \mathbb{Z}$. here it is easy to see, $ d=1$ .
Now,We let,the set $A$ is admissible containing m,n.So,if $ x^2 \in A$ , then,$ kx^2 \in A$ (from condition). if $ d=1. gcd(m^2,n^2)=1$ . According to hint ,we get $ am^2+bn^2=1$ by bezout's theorem. We get here $(am^2+bn^2)^2=1 \in A...(*)$, where k =2. & also $am^2 \in A, bn^2\in A.$ From (*), $ 1 \in A $ ; As, all multiples of $ m^2 \in A, so, k*1^2=k \in A.$ For this, all integers $ \in A.$ $ SO, A=\mathbb{Z} . $....... :D
How $am^2 \in A$?

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: IMO Shortlist 2012 N1

Unread post by nahin munkar » Sun Aug 07, 2016 11:56 am

asif e elahi wrote:
nahin munkar wrote:OK. I have approached it like this.
Let, $d= gcd(m,n).$ If, $d > 1$, if $d|x$ & $ d|y $ then $d|x^2+kxy+y^2 $ for all k.So,though the multiple of d satisfies condition, but $A \ne \mathbb{Z}$. here it is easy to see, $ d=1$ .
Now,We let,the set $A$ is admissible containing m,n.So,if $ x^2 \in A$ , then,$ kx^2 \in A$ (from condition). if $ d=1. gcd(m^2,n^2)=1$ . According to hint ,we get $ am^2+bn^2=1$ by bezout's theorem. We get here $(am^2+bn^2)^2=1 \in A...(*)$, where k =2. & also $am^2 \in A, bn^2\in A.$ From (*), $ 1 \in A $ ; As, all multiples of $ m^2 \in A, so, k*1^2=k \in A.$ For this, all integers $ \in A.$ $ SO, A=\mathbb{Z} . $....... :D
How $am^2 \in A$?

As, $ kx^2 \in A $ for all $ k $ if $ x \in A $ (calculation from condition). Here, $ m \in A $ . $ So $, $ am^2 \in A $.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: IMO Shortlist 2012 N1

Unread post by asif e elahi » Sun Aug 07, 2016 12:17 pm

There is no condition saying $kx^2 \in A$. You have to prove it. (Though the proof is very obvious).

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

Re: IMO Shortlist 2012 N1

Unread post by Phlembac Adib Hasan » Sun Aug 07, 2016 1:10 pm

Interesting sidenote: if I recall correctly, ISL 2012 A2 is somewhat similar in flavor.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: IMO Shortlist 2012 N1

Unread post by nahin munkar » Sun Aug 07, 2016 7:53 pm

asif e elahi wrote:There is no condition saying $kx^2 \in A$. You have to prove it. (Though the proof is very obvious).
$ OK $. if we let $ x=y $ of the condition. Then, a simple manipulation tells us that it is obvious $ (kx^2 \in A) $ for all $ k $ under admissible-set condition . Plugging, $ x=y $ of the defination, we now easily get the proof...... :D
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

Post Reply