Let a and b be positive integers. Then

- if is an integer, is a perfect square.
- if is an integer, .

The first problem was question 6 in the 1988 International Mathematical Olympiad. In this post we show these results, find the solutions (a,b) and look at how similar equations can be solved. The idea used is known in some circles as “Vieta jumping” or “root flipping” which is a form of descent, forming smaller solutions from bigger ones.

Solution of 1.(found in [1]) Fix k and rewrite the equation asBy symmetry we may assume . For all such pairs (a,b) of positive integers satisfying the equation, there is one such that is minimal. Let . We know that is one root of this quadratic, and the other is given by

From the first equation, is an integer.

a) If ,

a contradiction. Hence .

b) Suppose . Then satisfies the given equation and

However this contradicts the minimality assumption on , so we conclude that , and

a perfect square. This completes the proof of 1.

The general solution of problem 1 is found by using the fact that if (a,b) is a solution, so too is (b,kb-a). The above argument showed that , so a smaller solution is obtained. This recurrence can be continued until we reach the minimal solution. From the above argument, applying the recurrence one more time gives . Then from the equation we obtain . Reversing this recurrence gives us the solution from (a,b), leading to the general solution being adjacent terms of the sequence

where .

It can also be shown [1] that for any solution (a,b) of the equation, k is the square of the greatest common divisor of a and b.

Solution of 2.(found in [2]) Firstly we note that , soWe proceed as in the first problem. Assume a solution with minimal (the case can easily be shown to be impossible), then form the quadratic and instead of (1), arrive at the second root

By the minimality assumption . Hence is less than the roots of a positive quadratic polynomial, so Hence

from which

where the second inequality follows from (2). As and , we must have . Hence

from which or and in either case , as required.

As in problem 1, all solutions are found by a second order recurrence relation from the minimal solutions (2,1) and (3,1). In this case, the recurrence is , leading to adjacent terms of either of the following two sequences:

1,2,9,43,206,…

1,3,14,67,321,…

More generally, if we wish to solve the equation

in integers a and b (where n and k are integers with k > 2), there are either no solutions or infinitely many solutions. As above, we use the fact that if (a,b) is a solution, so is (b,kb-a). Then we need to determine whether such a transformation makes the solution smaller and when the process terminates. Also if (a,b) is a solution, so is (-b,-a).

One partial generalisation of problem 1 (found in [3]) is:

If , then there are solutions to , in integers a and b if and only if n is a perfect square.

To show this, if is the solution with minimal, form , which has roots and . By minimality, . The quadratic f(x) is decreasing for , and so if ,

From this contradiction, we conclude that , leading to , so n is a perfect square. Conversely, if , then (a,b) = (c,0) is a solution. This completes the proof. As before, all solutions can be found via a recurrence.

If n is negative, we can upper bound the minimal solution as follows. As in the proof of problem 2 above, , which leads to

This gives an upper bound on on which to try out solutions. If no such exists, there are no solutions to the equation. The case of k = -n = 5 in problem 2 for example led to the bound , from which was the sole candidate to try.

#### References and further reading

[1] Mathematical Olympiads, The 1988 Australian Scene

[2] Vieta Jumping related .. • Art of Problem Solving

[3] http://www.math.niu.edu/~rusin/known-math/00_incoming/quad_eqn

[4] N = (x^2 + y^2)/(1+xy) is a Square – Mathpages.com

## Leave a Reply