Conference rusure::math

>Q3.     A function f is defined on the positive integers by
>                f(1)    = 1,  f(3) = 3,
>                f(2n)   = f(n),
>                f(4n+1) = 2f(2n+1) - f(n),
>                f(4n+3) = 3f(2n+1) - 2f(n),
>for all positive integers n.
>Determine the number of positive integers n, less than or equal to 1988, for
>which f(n) = n.

The answer to Q3 can be calculated quickly with a BASIC program and appears 
to be 92. I'd hate to have to do the arithmetic with pencil & paper under
fire, but so far I don't have a shortcut. Were computers/calculators
permitted as tools in the exam? Even if there is a simple formula for f(n)
deducible from the recursion, there are still all those comparisons to be 
made...

Lynn 

     Re .1:
     
>> The answer to Q3 can be calculated quickly with a BASIC program and appears 
>> to be 92. I'd hate to have to do the arithmetic with pencil & paper under
     
     A VAX LISP program also counted 92.  They were all odd
     (which wouldn't have been too difficult to predict),
     they weren't all prime.
     
     Dan
     
         1         3         5         7         9
        15        17        21        27        31
        33        45        51        63        65
        73        85        93        99       107
       119       127       129       153       165
       189       195       219       231       255
       257       273       297       313       325
       341       365       381       387       403
       427       443       455       471       495
       511       513       561       585       633
       645       693       717       765       771
       819       843       891       903       951
       975      1023      1025      1057      1105
      1137      1161      1193      1241      1273
      1285      1317      1365      1397      1421
      1453      1501      1533      1539      1571
      1619      1651      1675      1707      1755
      1787      1799      1831      1879      1911
      1935      1967

    > Q6.     Let a and b be positive integers such that ab+1 divides a^2+b^2.
    > Show that (a^2+b^2)/(ab+1) is the square of an integer.
    
    This is easy once you figure out the trick.
    
    Lemma:  Modulo a prime number, f, the only numbers x such
    	that x^2 = y^2 are x=y and x=-y.
    
    Proof:
    	Clearly x=y works.  Let x be another number such that x^2
    	= y^2.  Let k=x-y.  Then y^2 = (y+k)^2 = y^2+2yk+k^2, so
    	k^2=-2yk.  k is not zero and must be relatively prime to f,
    	since f is prime, so there is a multiplicative inverse of
    	k.  So from k^2=-2yk, we get k=-2y, so x=y-2y=-y.
    
    Lemma:  If f is a prime that divides a^2+b^2 and ab+1, f is 2.
    
    Proof:
    	f divides ab+1, so ab=-1 (modulo f).
    	Clearly neither a nor b is zero modulo f, so they both have
    	inverses.  Multiplying ab=-1 by b's inverse, b', gives:
    	a = -b'.
    	Substitute for a into a^2+b^2 = 0 (modulo f) to get:
    	b^2 = b'^2.
    	b = b' modulo f or b = -b' modulo f, by lemma.
    	Multiply both sides of each of the above by b:
    	b^2 = 1 modulo f or b^2 = -1 modulo f.
    	Without loss of generality, let b^2 = -1 modulo f.
    	Since b^2 = -1, a^2 = 1.
    	Let i be such that i^2 = -1 modulo f.
    	By the lemma, b = i or b = -i.
    	Also by lemma, a = 1 or a = -1.
    	Consider all four possibilities for the pair of a and b:  (1,i),
    	(1,-i), (-1,i), (-1,-i).  The values these give for ab+1 are
    	i+1, -i+1, -1+i, and -1-i.  ab+1 is congruent to zero
    	modulo f.  Substitute in each of the four expressions and solve
    	for i; i = -1 or i = 1 modulo f.
    	Whether i is -1 or 1, i^2 is 1.  By definition of i, i^2 = -1,
    	so 1 = -1 modulo f, or 2 = 0 modulo f, so f is clearly two.
    
    So ab+1 must be a power of two.  Since a and b are positive, ab+1
    cannot be one, so ab+1 must be at least two.  Also, if a or b were
    even, ab+1 would be odd, which is impossible.
    
    We know a and b are odd; consider all their values modulo
    4:  (1,1), (1,3), (3,1), (3,3).  In each case, a^2+b^2 is 2 modulo
    4, so a^2+b^2 is not divisible by four.  ab+1 divides a^2+b^2, so
    ab+1 also cannot be divisible by four.
    
    ab+1 is a power of two which is at least two and not divisible by
    four, so it is exactly 2.
    
    Clearly a and b are each 1.
    (a^2+b^2)/(ab+1) = 2/2 = 1, which is the square of an integer.
                                                                     
    
    				-- edp

There's something wrong with .3, but I don't know what it is.

A counterexample is a=2, b=8, ab+1=17, a^2+b^2=68, quotient = 4.

I thought I had solved it too, even entered a solution, then realized my
error and quickly deleted it; sketch of my (partial) solution follows.

Use x|y to mean "x divides y".

ab+1 | a^2+b^2 --> ab+1 | a^4 + a^2*b^2 (mult numerator by a^2)
	       --> ab+1 | 2ab+1-a^4	(subt numerator from (ab+1)^2)

If (2ab+1-a^4)/(ab+1) = k, then:

If k=0 then ab+1=0, ab=-1. Impossible for positive a,b.

If k=1 then ab+1 = 2ab+1-a^4, ab=a^4, b=a^3. If b=a^3, ab+1 = a^4+1,
a^2 + b^2 = a^6 + a^2, and their quotient = a^2 is a perfect square.
So far so good.

If k=2 then 2ab+2 = 2ab+1-a^4, a^4 = -1. Impossible.

If k>2 then kab+k = 2ab+1-a^4, (k-2)ab= 1-k-a^4. Impossible for positive a,b.

That's what I posted, but I forgot that with all the numerator modifications
the numerator can be negative, so k can be negative. That's where I get into
trouble. When k is negative I can't prove anything...

>    	a = -b'.
>    	Substitute for a into a^2+b^2 = 0 (modulo f) to get:
>    	b^2 = b'^2.

Substituting yields b^2 = -b'^2....

> If k=0 then ab+1=0, ab=-1. Impossible for positive a,b.

should be:

If k=0 then 0 = 2ab+1-a^4, 1 = a*(a^3-2b), a must be +1 or -1, in
either case b=0 so no solutions in positive non-zero a,b.

    Re .5:
    
    I bet I kept the minus sign in "a = -b'" when I squared it.  It doesn't
    look like it is repairable, considering your counterexample. 
    
    
    				-- edp

     So far the only case I have found for this is where a = b^3,
     (or vice versa), in which case (a^2 + b^2) / (ab + 1) = b^2.
     Has anyone found any other examples where ab + 1 divides
     a^2 + b^2?
     
     Dan

Well, there's:
	a=8, b=30
	a=30,b=112 
	a=27,b=240
	a=112,b=418
etc.

Lynn Yarbrough 

     Wow!

(from Andrew Buchanan)

------------------------------------------------------------------------------
 
Q1.     Consider two coplanar circles of radii R and r (R > r) with the same
centre.  Let P be a fixed point on the smaller circle and B a variable point on
the larger circle.  The line BP meets the larger circle again at C.  The
perpendicular p to BP at P meets the smaller circle again at A (if p is tangent
to the circle at P then A = P).
(i) Find the set of values of (BC)^2 + (CA)^2 + (AB)^2.
        [ (BC)^2 means the square of the distance from B to C. ]
(ii) Find the locus of the midpoint of AB.

A1.	Choose a coordinate frame as follows.   O, the centre of the two 
planar circles, lies at the origin.   AP is parallel to the x-axis, and hence
the perpendicular BC is parallel to the y-axis.

	A is at (-x,  y)
	B is at ( x,  Y)
	C is at ( x, -Y)
	P is at ( x,  y)  and while we're at it, let M be midpoint of AB
	M is at ( 0, (Y+y)/2)

	We know R^2 = x^2 + Y^2
	      & r^2 = x^2 + y^2

(i) (AB)^2 + (AC)^2 + (BC)^2  =
	4*x^2 + (Y-y)^2 +
	4*x^2 + (Y+y)^2 +
	4*Y^2        	      =
	8*x^2 + 6*Y^2 + 2*y^2 =

	6*R^2 + 2*r^2

(ii) Change coordinate frame to one in which O at origin, and P at (r,0). 
Locus of B is a circle.   Any triangle satisfying criteria in problem 
statement could have B & C relabeled as one another, and still satisfy the 
criteria.   Hence locus of C is a circle.

(MO) = (PC)/2.   Angle MOP = Angle OPC.   So if we define N as the midpoint
of OP, then triangle OPC is similar to triangle NOM.   Locus of P is circle 
radius R centre O.   So Locus of M is circle R/2 centre N at (r/2,0).

------------------------------------------------------------------------------
 
Q2.     Let n be a positive integer and let A[1], A[2], ..., A[2n+1] be subsets
of a set B.  Suppose that
(a) each A[i] has exactly 2n elements,
(b) each A[i]_intersect_A[j] (1 <= i < j <= 2n+1) contains exactly one element,
(c) every element of B belongs to at least two of the A[i].
For which values of n can one assign to every element of B one of the numbers 0
and 1 in such a way that each A[i] has 0 assigned to exactly n of its elements?

A2.	Suppose b in B belongs to more than two A[i], wlog A[0], A[1] & A[2].
Then X[0] = A[0]^A[1] v A[0]^A[2] v ... v A[0]^A[2n+1], where 'v' is union, 
'^' is intersection and '^' binds before 'v'.   Since b is in A[1] & A[2], by
statement (b) above the number ov elements in X[0] < 2n.   So, by (a), there
is an element in A[0] which is not in any other A[i].   But this contradicts
(c).   So by reductio ad absurdum, each element of B belongs to exactly two
of the A[i].

	Label the unique element of B which is in A[i] and A[j], b{i,j}.
Call the A[i] vertices, and the b{i,j} edges.   Define b{i,j} is incident with 
the edges A[i] and A[j] only.   Suppose that the elements of B have been 
assigned 0 or 1 suitably.   Then each vertex is incident with the same number 
of 0-edges as 1-edges.   Summing over all the vertices, and dividing by 2,
there are the same number of 0-edges in B as 1-edges.   The total number of 
edges, i.e. elements in B, is (2n+1)*n.   If n is odd, this total is odd, and
cannot be partitioned evenly into two subsets.

	What if n is even?   Say that b{i,j} is assigned value 1 iff 
abs(i-j mod (2n+1)) > n/2, otherwise b{i,j} is assigned value 0, where x mod 
2n+1 is in the range {-n, -n+1..., 0, ... n-1, n}.   Clearly, each vertex is 
incident to exactly n 1-edges, and n 0-edges.
  
-------------------------------------------------------------------------------
 
Q3.     A function f is defined on the positive integers by
                f(1)    = 1,  f(3) = 3,
                f(2n)   = f(n),
                f(4n+1) = 2f(2n+1) - f(n),
                f(4n+3) = 3f(2n+1) - 2f(n),
for all positive integers n.
Determine the number of positive integers n, less than or equal to 1988, for
which f(n) = n.

A3.	For odd integers >= 3, define the function, g, as follows:

g(2m+1) = f(2m+1) - f(m)

	This means we can rephrase the recursive definitions of f as:

g(2m+1) = ( m even:  2*g(m+1)
	  (
	  ( m odd:   2*g(m)

	Expressing numbers in binary notation, and using 'string' to denote an 
arbitrary string of 0's and 1's, and using '?' to denote a single unknown
bit, this can be written:

g(string?1) = 2*g(string1).   I.e. to compute g, remove a bit, and multiply 
by 2.   Therefore if n has exactly a bitits, then g(n) = 2^a.   [g(3) = 2]

Now from the definition of g, and the definition of f for even numbers:

f(string0) =  0*2^a + f(string)
f(string1) =  1*2^a + f(string)

So f(n) is rev(n), i.e. n as a binary number has the bits reversed in order.

What numbers <= 1988 are palindromes?   It is exactly these for which f(n) = 
n.

range   number of bits   number of palindromes
==============================================
1 to 1          1               1
2 to 3		2		1
4 to 7		3		2
8 to 15		4		2
16 to 31	5		4
32 to 63	6		4
64 to 127	7		8
128 to 255	8		8
256 to 511	9		16
512 to 1023	10		16
1024 to 2047	11		32
			Total = 94

	However, we must remove those between 1989 and 2047.   All numbers 
between these values are of the form 11111abcdef when written in binary.   So
the palindromes are of the form 11111a11111.   Therefore there are two of 
them.   The total number of n s.t. n=f(n) is therefore 92.

-------------------------------------------------------------------------------
 
Q4.     Show that the set of real numbers x which satisfy the inequality
           SUM(k=1..70) k / (x - k)   >=  5/4
is a union of disjoint intervals, the sum of whose lengths is 1988.

A4.	How does the function f(x) = SUM(k=1..70) k / (x - k) behave?   It is
undefined for x = 1..70, and in each interval (i,i+1) (i=1,..69) it is 
continuous, running from +infinity to -infinity.   For x < 1, f(x) is 
negative.   For x > 70, f(x) is positive, running from +infinity 
asymptotically to zero.

	Therefore, there are seventy disjoint intervals for which f(x) > 5/4.
These are (i,c(i)), where for i..69, c(i) < i+1.   We wish to calculate:

	L = SUM(k=1..70) c(k) - k
	  = -K + SUM(k=1..70) c(k)

where K = SUM(k=1..70) k.

	But the c(k) are simply the roots of the equation:

f(x) = 5/4,

and if we multiply this equation by P(x) = PRODUCT(k=1..70) x-k, we get a 
polynomial of degree 70 in x:

P(x).f(x) - 5*P(x)/4

	We actually want the sum of the roots of this equation, which is of
course:
	-(coefficient of x^69)/(coefficient of x^70)

=	-(K + (5/4)K)/(-(5/4)K)
=	(9/5)K

So L = (9/5)K - K = (4/5)K = 1988
 
-------------------------------------------------------------------------------
 
Q5.     ABC is a triangle right-angled at A, and D is the foot of the altitude
from A.  The straight line joining the incentres of the triangles ADB, ACD
intersects the sides AB, AC at the points K, L respectively.  S and T denote the
areas of the triangles ABC and AKL respectively.  Show that S >= 2T.

A5.	Select coordinate frame with A at origin, B at (b,0), C at (0,c).
First question: where is D?

	The equation of the line BC is:  
cx + by = bc
	So the equation of the orthogonal AD is
cy = bx
	Hence D is at (b(c/h)^2, c(b/h)^2) where h is the length of BC.
The length of AD is bc/h.   The length of CD is (c^2)/h, in proportion.
Now consider F, the incentre of ACD.   Drop perpendiculars to the three sides
which hit AC at P, CD at Q and DA at R respectively.   It is immediate that
the lengths AP = AR, CP = CQ, and DQ = DR.   Call these lengths l1, l2 and l3
respectively.   Then:

l1 + l2 = c
l1 + l3 = bc/h
l2 + l3 = (c^2)/h

	Since Angle APF is right, the coordinates of F are (l3,l1).
i.e. F is at:

	( (bc/h + (c^2)/h - c)/2 , (bc/h - (c^2)/h + c)/2 )

By symmetry, E, the incentre of ABD is at:

	( (bc/h - (b^2)/h + b)/2 , (bc/h + (b^2)/h - b)/2 )

	The equation of the line passing through (x1,y1) & (x2,y2) is:
(x-x1)*(y-y2) = (x-x2)*(y-y1).   At L, x=0, so:

	(x1 - x2)*y = x1y2 - x2y1.

Substituting:
	y*(c^2 + b^2 - ch - bh)/2h = bc*(b^2 + c^2 - ch - bh)/2(h^2)

i.e.	y = bc/h.

If L is at (0, bc/h), then by symmetry M is at (bc/h, 0), i.e. the triangle
LOM is half a square!   S/T = bc/(bc/h)^2 = (h^2)/bc.   It merely remains
to find the mimimum of this:

(b-c)^2 >= 0 ==> h^2 >= 2bc.   So S/T >= 2.
  
-------------------------------------------------------------------------------
 
Q6.     Let a and b be positive integers such that ab+1 divides a^2+b^2.
Show that (a^2+b^2)/(ab+1) is the square of an integer.

A6.	Suppose that d = (a^2+b^2)/(ab+1).   
If a=b then to preserve integrality of d, a must be 1, and d = 1 (a square).   
So say a > b.   We now have a quadratic:

	a^2 + b^2 - dab - d = 0. 

Solve this quadratic for a:

	a = (db +- sqrt((d^2 -4)*(b^2) + 4d))/2

Say c is the *other* root of this expression.   Now:

	ca = b^2 - d < b^2

	c < (b^2)/a < b

a+c is an integer, so c is an integer

So if (a,b) is one solution to the problem, so is (b,c) with the same value 
of d.   And one can clearly carry on leap-frogging to smaller and smaller 
solutions.   Let's call a sequence (va,vb,vc,vd,ve...) such that (va,vb), 
(vb,vc), (vc,vd), (vd,ve)... are all solutions to our problem a descending 
chain.   What happens 'in the end'?

First, is it possible that the determinant becomes zero?   No, because then
a=c, but we know that b comes between them.   The only other possibility is
that c may become zero or negative.

c <,= or > 0 as b^2 <,= or > d.

A digression to investigate b^2-d:

ab+1 | (b^2)*(a^2 + b^2) - (ab-1)*(ab+1) =>
ab+1 | b^4 + 1				 =>
ab+1 =< b^4 + 1				 =>
a =< b^3

ab+1 | b*(a^2 + b^2) - a*(ab+1)		 =>
ab+1 | b^3 - a				 =>  (since a =< b^3)

Two possibilities: 
(i) a = b^3

(ii) ab+1 =< b^3 - a			 =>
a(b+1) < b^3				 =>
a < b^3/(b+1) < b^2
Now
d*(ab+1) = (a^2 + b^2)			 =>
d = (a^2 + b^2)/(ab+1) < (a^2 + b^2)/ab < 2a^2/ab < 2a/b < 2b^2/b < 2b < b^2

So in summary d =< b^2, and equality is attained iff a = b^3.   All descending 
chains will end in a pair of the form (b^3, b).   d is b^2, i.e. a square.   
Since d is constant over a descending chain, we have the result.

------------------------------------------------------------------------------ 

     re .-1
     
     A small nit for Q2.  The sequence A[i] is defined only
     for i = 1, ..., 2n+1 in the problem statement, but the
     answer seems to take it as running from i = 0, ..., 2n.
     So change X[0] and A[0,], A[1], A[2] in  the answer to
     X[1] and A[1], A[2], A[3].  The union of intersections
     in the answer is a union of 2n intersections in either
     case.  Each intersection contains exactly one element,
     and the element from A[1]^A[2] equals the element from
     A[1]^A[3], so the union has less than 2n elements ....
     
     Dan

A2.  I had a hard time with the first part of this answer.  Here's a
     better stab at it.

Suppose b in B belongs to more than two A[i], wlog A[1], A[2] & A[3].

Let
      X	= A[1]^A[2] v A[1]^A[3] v A[1]^A[4] v ... v A[1]^A[2n+1]
	=     b     v     b     v A[1]^A[4] v ... v A[1]^A[2n+1]
	=                 b     v A[1]^A[4] v ... v A[1]^A[2n+1]

But | A[i]^A[j] | = 1, for i <> j, so
	
    |X|	<=  |b| + |A[1]^A[4]| + ... + |A[1]^A[2n+1]|
    |X| <=  1 + (2n+1 - 3) = 2n - 1
    |X| <= 2n - 1

Now, the set difference A[1]-X[1] is non-empty:

    |A[1]-X| >= |A[1]| - sup(|X|) >= 2n - (2n-1) = 1.

Let z be an element A[1] that is not in X (an element of the set difference).
By (c), z must belong to at least one other A[i] besides A[1].  Thus, some
A[1]^A[i] (with i > 1) must include z, and so X must include z.
This is a contradiction -- therefore there is no b in B belonging to
more than two A[i].  So each element of B belongs to exactly two A[i].

     I haven't been receiving much USENET stuff lately, so I
     suppose that I missed most of the replies there, except for
     these and an answer for the ab+1 problem that was much like
     the one here. 
     
     Dan
     
Newsgroups: sci.math
Path: decwrl!ucbvax!pasteur!helios.ee.lbl.gov!lll-tis!ames!pacbell!att!mtunj!io!tmk
Subject: Re: unofficial report from the International Mathematical Olympiad
Posted: 21 Jul 88 15:16:23 GMT
Organization: AT&T, Middletown, NJ
 
In article <[email protected]> [email protected] (Brendan McKay) writes:
>The 1988 IMO is just now winding up.  It was contested by about 260 students
>from 49 countries.  (These are students in the final years of secondary
					^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>school).
>
>Brendan McKay.
 
Not necessary to be in the final year. The requirement is "pre-college".
In fact, I believe there are about 50% of the contestants are not yet in
the 12th grade.
There was once an 8th grader from USA and a 10-year old boy from Australia
competing in this event.
 
-tmk

     *****************************************************************

Newsgroups: sci.math
Path: decwrl!labrea!eos!ames!think!bloom-beacon!bu-cs!buengc!bph
Subject: Re: Problems from the International Mathematical Olympiad
Posted: 21 Jul 88 22:05:21 GMT
Organization: Boston Univ. Col. of Eng.
 
In article <[email protected]> [email protected] (Brendan McKay) writes:
>
>Here are the problems from the International Mathematical Olympiad, just
>
>[...]
>
>from A.  The straight line joining the incentres of the triangles ADB, ACD
 
Okay, I'll bite:  what is an "incentre?"
 
				--Blair

     *****************************************************************

Newsgroups: sci.math
Path: decwrl!purdue!mailrus!cornell!batcomputer!itsgw!imagine!pawl5.pawl.rpi.edu!entropy
Subject: Re: unofficial report from the International Mathematical Olympiad
Posted: 22 Jul 88 06:40:14 GMT
Organization: 
 
In article <[email protected]> [email protected] (Brendan McKay) writes:
>  The gradings are still being finalised as I type, but it looks
>like the top team placings are
>	USSR China Romania West Germany Vietnam USA Bulgaria	
>[This list is 100% unofficial and may even be wrong.]
>
  Assuming it's right, isn't this the second year in a row that Vietnam has
made the top six?  The others don't surprise me as much, but I had never
associated Vietnam with wither mathematics in general or with the IMO in
particluar before.  Could someone comment on this?  Is't a fluke, or something
more?
 
  M-J. Dominus
  [email protected]       [email protected]

Newsgroups: sci.math
Path: decwrl!labrea!agate!helios.ee.lbl.gov!lll-tis!lll-winken!uunet!mcvax!prlb2!kulcs!kulesat!esat!kulmath!vanroose
Subject: Re: Problems from the Int. Mathematical Olympiad
Posted: 12 Aug 88 17:05:03 GMT
Organization: Katholic Univ. of Leuven - Department of Mathematics, Belgium
 
In article <[email protected]>, [email protected] (Brendan McKay) posted the
problems from the 1988 International Mathematical Olympiad, held in Canberra.
 
I tried question 6 (the hardest one, as was said), and here is what I found.
 
Let me first repeat the question:
> 
> Q6.     Let a and b be positive integers such that ab+1 divides a^2+b^2.
> Show that (a^2+b^2)/(ab+1) is the square of an integer.
> 
By the way, did *you* already try to prove this?
I would suggest you first work on it, before reading further on.
 
                           Peter Vanroose ([email protected])
                           Department of Mathematics, K.U.Leuven,
                           Belgium.

 
 
 
 
 
 
 
 
In what follows, a, b and m stand for positive integers (eventually zero).
 
Call (a,b,m) a ``good'' triple if      (ab+1)m = a^2 + b^2.
We have to prove that for a good triple (a,b,m), m is always a square.
Notice that m is never 0, except when both a and b are 0.
 
Lemma 1:  If (a,b,m) is a good triple, then also (b,a,m).
 
Lemma 2:  If (0,b,m) is a good triple, i.e. a=0, then  m = b^2.
 
Lemma 3:  If (a,b,m) is a good triple, then also (a , am-b , m).
          Moreover, if a > 0, then am-b >= 0.
 
   Proof: Suppose (a,b,m) is a good triple, i.e., (ab+1)m = a^2 + b^2.
          1.  (ab+1) m = a^2 + b^2  <==>  ((am-b)a+1)m = (am-b)^2 + b^2
                    (this is elementary calculus)
          2.  am-b is certainly an integer, so it suffices to prove that
              am-b > -1.  Suppose for a moment that am-b <= -1.
              Then (ab+1)(am-b+1) <= 0  (because ab+1 > 0), so
              a(a^2+b^2) <= (ab+1)(b-1), or a^3+1 <= b(1-a),
              which is impossible because a^3+1 > 1, while b(1-a) <= 0.
 
Lemma 4: If (a,b,m) is a good triple with  0 < a <= b, and b'=am-b, then 
           (a,b',m) is a good triple with 0 <= b' < a.
 
   Proof: Suppose  0 < a <= b  (so m > 0).
          Using lemma 3, we only have to prove that am-b < a.
          Notice that  (a^2-1)a < (a^2+1)b ,  so   a^3-b < (ab+1)a ,
          so  a^3 + a b^2 < a^2 b +a+b + a b^2 ,
          so  am(ab+1) < (a+b)(ab+1) ,  so  am < a+b.
          
Conclusion:  suppose you are given a ``good'' triple (a,b,m), and you
have to prove that m is square.  Eventually interchange a and b, such 
that a <= b (see lemma 1).  If a=0, you are done, because of lemma 2.
If a > 0, apply lemma 4 to get a new ``good'' triple (a,b',m), with
b' smaller than before.  Repeat this procedure, until a or b is 0.
(This has to happen, because a and b are both strictly decreasing 
after two steps, but they remain positive.)
Then, because of lemma 2, m is square, which proves the whole story.
 
P.S.
Did someone find a (completely) different and/or shorter proof?
Let it know to the interested people!
                                            Peter.

 
> Lemma 3:  If (a,b,m) is a good triple, then also (a , am-b , m).
>           Moreover, if a > 0, then am-b >= 0.
 
>    Proof: Suppose (a,b,m) is a good triple, i.e., (ab+1)m = a^2 + b^2.
>           1.  (ab+1) m = a^2 + b^2  <==>  ((am-b)a+1)m = (am-b)^2 + b^2
>                     (this is elementary calculus)

But it has an elementary typo - should read:

		...  <==> ((am-b)a+1)m = (am-b)^2 + a^2

Its just a transcription error, tho - the proof of the lemma is good.

    re .18
    
    The hardest question of this paper (apparently) was the last viz.
    
    Prove that ab+1 | a�+b� => (a�+b�)/(ab+1) is a perfect square.
    
    Deducible from the various proofs is the conclusion that all pairs
    (a,b) satisfying ab+1 | a�+b�, excluding (1,1), are generated as follows.
    
    Let {a[n]} be a sequence defined by
    
    a[1] = t
    a[2] = t�
    a[n] = t�.a[n-1] - a[n-2], n >= 3
    
    where t is an arbitrary integer with t > 1
    
    then (a[n],a[n-1]) satisfies the condition for all n > 1 and any t as above.
    
    For those who like their expressions ugly this can be solved in closed
    form as
                                         n                   n
    		t      / /t�+sqrt(t^4-4)\    /t�-sqrt(t^4-4)\  \
    a[n] = ----------- | |--------------|  - |--------------|  |
    	   sqrt(t^4-4) \ \      2       /    \      2       /  /
    
    EEFTR: Show that this expression is 'always ugly' i.e. sqrt(t^4-4) is
           always irrational.