Advanced book on Mathematics Olympiad

5.1 Integer-Valued Sequences and Functions 249

Prove thatSmust equal the set of all integers.

Solution.This problem was submitted by K. Kedlaya and L. Ng. The solution below
was discovered by M. Ince and earned him the Clay prize.
First thing, note that ifb 1 ,b 2 ,...,bmare some integers that generateSand satisfy
the three conditions from the statement, thenbi− 2 bjand 2bi−bjare also inSfor
any indicesiandj. Indeed, sincebi,bj, andbi−bjare inS, by (iii) we have that
bi− 2 bj∈S. Moreover, fori=jin (ii) we find that 0=bi−bi∈S. Hence applying
(iii) tox∈Sand 0 we have that−x∈Sas well, and in particular 2bi−bj∈S.
Ann-tuple(b 1 ,b 2 ,...,bn)as above can be substituted by(b 1 ,b 2 −b 1 ,...,bn−b 1 ),
which again generatesSand, by what we just proved, satisfies (i), (ii), and (iii). Applying
this step to(|a 1 |,|a 2 |,...,|an|)and assuming that|a 1 |is the smallest of these numbers,
we obtain anothern-tuple the sum of whose entries is smaller. Because we cannot have
an infinite descent, we eventually reach ann-tuple with the first entry equal to 0. In the
process we did not change the greatest common divisor of the entries. Ignoring the zero
entries, we can repeat the procedure until there is only one nonzero number left. This
number must be 1.
From the fact that 0, 1 ∈Sand then also− 1 ∈S, by applying (iii) tox=1,y=− 1
we find that 2∈S, and inductively we find that all positive, and also all negative, integers
are inS. We conclude thatS=Z. As I. Kaplansky said, “An elegant proof hits you
between your eyes with joy.’’ 

706.Show that no positive integersx, y, zcan satisfy the equation

x^2 + 10 y^2 = 3 z^2.

707.Prove that the system of equations

x^2 + 5 y^2 =z^2 ,

5 x^2 +y^2 =t^2

does not admit nontrivial integer solutions.

708.Show that the equation

x^2 −y^2 = 2 xyz

has no solutions in the set of positive integers.

709.Prove that there is no infinite arithmetic progression whose terms are all perfect
squares.

710.Letfbe a bijection of the set of positive integers. Prove that there exist positive
integersa<a+d<a+ 2 dsuch thatf(a)<f(a+d)<f(a+ 2 d).