Advanced book on Mathematics Olympiad

Number Theory 679

Let us verify first that 0<r. Assume the contrary. Sincebr=a^2 −ka+1, we

must havea^2 −ka+ 1 ≤0. The equality case is impossible, sincea(k−a)= 1

cannot hold ifk≥3. Ifa^2 −ka+ 1 <0, the original divisibility condition implies

b(b−ak−k)=ak−a^2 − 1 >0, henceb−ak−k>0. But thenb(b−ak−k) >

(ak+k)· 1 >ak−a^2 −1, a contradiction. This proves thatris positive. From the fact

thatbr=a^2 −ka+ 1 <a^2 andb≥a, it follows thatr<a. Successively, we obtain the

sequence of pairs of solutions to the original problem(a 1 ,b 1 )=(a, b),(a 2 ,b 2 )=(r, a),

(a 3 ,b 3 ),...,withai≤bianda 1 >a 2 >a 3 >···,b 1 >b 2 >b 3 >···,which of

course is impossible. This shows that the ratio ofa^2 +b^2 +1toab+a+bcannot be

greater than or equal to 3, and so the answer to the problem consists of the pair( 1 , 1 )

together with all pairs of consecutive perfect squares.

(Mathematics Magazine)

713.We argue by contradiction: assuming the existence of one triple that does not satisfy

the property from the statement, we construct an infinite decreasing sequence of such

triples. So let(x 0 ,y 0 ,z 0 )be a triple such thatx 0 y 0 −z^20 =1, but for which there do

not exist nonnegative integersa, b, c, dsuch thatx 0 =a^2 +b^2 ,y 0 =c^2 +d^2 , and

z 0 =ac+bd. We can assume thatx 0 ≤y 0 , and alsox 0 ≥2, for ifx 0 =1, then

x 0 = 12 + 02 ,y 0 =z^20 + 12 , andz 0 =z 0 · 1 + 0 ·1. We now want to construct a new

triple(x 1 ,y 1 ,z 1 )satisfyingx^21 y 12 −z^21 =1 such thatx 1 +y 1 +z 1 <x 0 +y 0 +z 0. To this

end, setz 0 =x 0 +u. Then

1 =x 0 y 0 −(x 0 +u)^2 =x 0 y 0 −x 02 − 2 x 0 u+u^2

=x 0 (y−x 0 − 2 u)−u^2 =x 0 (x 0 +y 0 − 2 z 0 )−(z 0 −x 0 )^2.

A good candidate for the new triple is(x 1 ,y 1 ,z 1 )withx 1 =min(x 0 ,x 0 +y 0 − 2 z 0 ),
y 1 =max(x 0 ,x 0 +y 0 − 2 z 0 ),z 1 =z 0 −x 0. Note thatx 1 +y 1 +z 1 =x 0 +y 0 −z 0 <
x 0 +y 0 +z 0.
First, let us verify thatx 1 ,y 1 ,z 1 are positive. From

z^20 =x 0 y 0 − 1 <x 0 y 0 ≤

(

x 0 +y 0

2

) 2

we deduce thatx 0 +y 0 > 2 z 0 , which means thatx 0 +y 0 − 2 z 0 >0. It follows that both

x 1 andy 1 are positive. Also,

z^20 =x 0 y 0 − 1 ≥x 02 − 1 ,

which implies(z 0 −x 0 )(z 0 +x 0 ) ≥−1. Sincez 0 +x 0 ≥ 3, this can happen only

ifz 0 ≥x 0. Equality would yieldx 0 (y 0 −x 0 )=1, which cannot hold in view of the

assumptionx 0 ≥2. Hencez 1 =z 0 −x 0 >0. If the new triple satisfied the condition

from the statement, we would be able to find nonnegative integersm, n, p, qsuch that