IMO 2012 Shortlist N1

Category: Number Theory

Problem

Call admissible a set A of integers that has the following property: If x,y ∈ A (possibly x = y) then x2

kxy + y2 ∈ A for every integer k. Determine all pairs m,n of nonzero integers such that the only admissible set containing both m and n is the set of all integers. Solution. A pair of integers m,n fulfills the condition if and only if gcd(m,n) = 1. Suppose that gcd(m,n) = d > 1. The set A = {...,−2d,−d,0,d,2d,...} is admissible, because if d divides x and y then it divides x2
kxy + y2 for every integer k. Also m,n ∈ A and A 6= Z. Now let gcd(m,n) = 1, and let A be an admissible set containing m and n. We use the following observations to prove that A = Z: (i) kx2 ∈ A for every x ∈ A and every integer k. (ii) (x + y)2 ∈ A for all x,y ∈ A. To justify (i) let y = x in the definition of an admissible set; to justify (ii) let k = 2. Since gcd(m,n) = 1, we also have gcd(m2 ,n2 ) = 1. Hence one can find integers a,b such that am2
bn2 = 1. It follows from (i) that am2 ∈ A and bn2 ∈ A. Now we deduce from (ii) that 1 = (am2
bn2 )2 ∈ A. But if 1 ∈ A then (i) implies k ∈ A for every integer k.43