## IMO Shortlist 2012 N1

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

### IMO Shortlist 2012 N1

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.

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

### Re: IMO Shortlist 2012 N1

Hint:
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

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

### Re: IMO Shortlist 2012 N1

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} .$.......
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

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

### Re: IMO Shortlist 2012 N1

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} .$.......
How $am^2 \in A$?

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

### Re: IMO Shortlist 2012 N1

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} .$.......
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

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

### Re: IMO Shortlist 2012 N1

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

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

### Re: IMO Shortlist 2012 N1

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

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

### Re: IMO Shortlist 2012 N1

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......
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss