1988 IMO Problem 6

Problem 6 of the 1988 International Math Olympiad reads:

Let a and b be positive integers such that a b + 1 divides a^2 + b^2.  Show that \displaystyle\frac{a^2 + b^2}{a b + 1} is the square of an integer.

There’s a writeup of a solution at the Art of Problem Solving wiki, but I found it incredibly sketchy and difficult to read and the article was locked, so here’s what’s hopefully an easier-to-read exposition of the same solution:

In other words, we’d like to show that any solution in positive integers to the equation a^2 + b^2 = c(a b + 1) has c a perfect square.

First, suppose we have a solution with a = b.  Then a^2 + 1 divides 2 a^2. Applying the Euclidean algorithm,

\gcd(a^2 + 1, 2 a^2) = \gcd(a^2 - 1, a^2 + 1) = \gcd(2, a^2 - 1) \in \{1, 2\}

so we must have a^2 + 1 = \{1, 2\}.  Since a is positive, we must have a=1.  In this case, a^2 + 1 = 2a^2 = 2 so c = 1 which is a perfect square.  So we may assume in what follows that a \neq b.

Fix a positive integer c for which the equation has solutions in the positive integers, and let (a, b, c) be such a solution with the minimum possible value of a.  Note that by symmetry we must have a < b, since otherwise (b, a, c) is a solution with a smaller first coordinate.

Rewrite the equation as

b^2 - c a b + (a^2 - c) = 0

and notice that this says that b is a root of the quadratic equation

x^2 - c a x + (a^2 - c) = 0

Let r denote the other root.  Then b + r = c a and b r = a^2 - c.  It follows that r = c a - b is an integer, and that

a r < br = a^2 - c \leq a^2

So r < a.  This must mean that r \leq 0, as otherwise the solution (r, b, c) to the original equation would contradict the minimality of a.

Now

(b+1)(r + 1) = b r + (b + r) + 1 = (a^2 - c) + c a + 1 = a^2 + c(a - 1) + 1 \geq 1

Since b + 1 is positive, we must have r + 1 positive as well.  Since r is an integer, we must have r = 0, so

a^2 - c = b r = 0

or in other words c = a^2.

 

Advertisements
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s