Exercise 1.2.54** (Legendary problem)

Let a and b be positive integers such that ( 1 + ab ) ∣ ( a 2 + b 2 ) . Show that the integer ( a 2 + b 2 ) ∕ ( 1 + ab ) must be a perfect square.

Answers

I reproduce here the solution of Dr John Campbell (Canberra, 1988), without modification except for an obvious typo.

http://www.wfnmc.org/mc19882campbell.pdf

A SOLUTION TO 1988 IMO QUESTION 6.

(The Most Difficult Question Ever Set at an IMO)

Theorem

If a , b are integers ≥ 0 such that

q = a 2 + b 2 ab + 1

is integral, then

q = ( GCD ( a , b ) ) 2 .

Proof. If ab = 0 (i.e. if a = 0 or b = 0 ) the result is plain. This suggests using induction on ab .

If ab > 0 , we may suppose (from the symmetry of the problem) that a ≤ b , and the result proven for smaller values of ab .

The next step is to find and integer c satisfying

q = a 2 + c 2 ac + 1 (1)

and

0 ≤ c < b . (2)

It will then follow by induction (since ac < ab ) that

q = ( GCD ( a , c ) ) 2 .

To obtain c , we solve

a 2 + b 2 ab + 1 = a 2 + c 2 ac + 1 = q .

Because these ratios are equal, we may subtract numerators and denominators to give

b 2 − c 2 ab − ac = q ,

i.e.

b + c a = q (since we want  c ≠ b )

so that

c = aq − b .

Notice that c is an integer, and

GCD ( a , c ) = GCD ( a , b ) .

Therefore the proof will be finished if we can prove (2).

To prove (2) we note, on the one hand, that

q = a 2 + b 2 ab + 1 < a 2 + b 2 ab = a b + b a

giving

aq < a 2 b + b ≤ b 2 b + b (since  a ≤ b ) = 2 b

Thus

aq − b < b ,

i.e.

c < b .

On the other hand

q = a 2 + c 2 ac + 1

implies

ac + 1 > 0

implies

c > − 1 a

implies

c ≥ 0 (since  c  is integral!) .

This completes the proof. □

(Some further remarks are given in the original paper.)

User profile picture
2024-06-19 08:32
Comments