From: steiner@andy.bgsu.edu (Ray Steiner)
Subject: Re: A Problem
Organization: Bowling Green State University B.G., Oh.
Date: Fri, 11 Dec 1992 21:33:07 GMT

steiner@andy.bgsu.edu (Ray Steiner) writes:

>hsieh@math.toronto.edu (Paul Hsieh) writes:

>>(Alexander Burshteyn) writes:
>>>Here is a nice problem, which was given, I believe, at the International High
>>>School Student Olympiad in Australia (I'm not sure about the exact title of the
>>>the competition, though).
>>>
>>>Prove that if, for some non-negative integers A and B, we have that
>>>(A^2 + B^2) / ( 1 + AB)  is an integer, then it is a square of an integer.
>>>
>>>Enjoy,
>>>
>>>Alex Burshteyn.


>>Actually, this appeared on an IMO question a few years ago.  Just for fun some
>>of us at U(T) tried solving the question from scratch (without looking up the
>>solution somewhere).  But we cheated by running a computer program for ages to
>>find examples.  We quickly came to the conjecture that the only possible (a,b)
>>was (p,p^3), but this is shot down by the example (30,8).  But after further
>>examimation of the data, Ed Dolittle saw the following:
>>If (a,b,k) is a solution where, (a^2+b^2)/(1+a*b)=k, and a,b,k are non-negative
>>integers, with a>=b, then so is (|a-k*b|,b,k).  Using this observation we see
>>that if (a,b,k) is a solution then we can find a different solution (c,d,k)
>>with c<=a, d<=b.  Applying this succesively we find that eventually one of
>>a or b will become 0 => k = a^2 or k=b^2.  (Note that throughout, k does not
>>change which is the important point of the procedure).  QED.
>>Now, I enjoy doing problems as much as the next guy, but the question I have,
>>is:  How in the heck is someone supposed to see this under contest conditions?
>>If you tried to find examples by hand, you'd be hard pressed, as there are
>>no non-trivial (meaning (p,p^3)-type examples) examples which are small,
>>besides (30,8).  And seeing that reducing step, in my mind, is not at all
>>obvious without looking at some examples.  My recollection is that very few
>>people got this question when it appeared at the IMO and I am surprised that
>>anyone did!  Hats off to those that did.  Anyways, that's about enough
>>bandwidth for me,

>>Paul Hsieh

>But, aren't we getting away from the original problem here?
>Neither this reply nor the previous one solves the ORIGINAL
>problem! The infinite descent argument indeed proves that
>a(or b) must eventually be zero, but ignores all other possible
>values of a and b. The division argument given in another
>post is also wrong, because of the solution (30,8). I tried
>solving the problem by computing the discriminant of the quadratic
>a^2-kab+(b^2-k)=0 and noting that it must be a square, but
>this didn't lead anywhere either! Surely,  the examiners
>who set this question must have had a simpler idea in mind!
>Ray Steiner

>-- 
>steiner@andy.bgsu.edu

Oops: Repost: My idea does lead somewhere after all!
If the discriminant of the quadratic above = c^2, then we
get 
c^2-(k^2-4)b^2= 4k.
If k is a square, k^2-4 isn't, so if k is a square we get 
infinitely many solutions! Just replace 4k by 1, solve the
basic Pell equation and then multiply each of c and b by 2\sqrt(k).
So now the problem is to show: If k is not a square this
equation has no integer solutions. If k is not a square mod 5
this is easy! But how does one prove this in general???
Ray Steiner

-- 
steiner@andy.bgsu.edu
Xref: sparky sci.math:16850 rec.games.abstract:620