Chaitanya's Random Pages

June 27, 2011

Filed under: mathematics — ckrao @ 9:26 pm

Let a and b be positive integers. Then

1. if $\displaystyle \frac{a^2 +b^2}{ab+1} = k$ is an integer, $k$ is a perfect square.
2. if $\displaystyle \frac{a^2 +b^2}{ab-1} = k$ is an integer, $k = 5$.

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 as

$\displaystyle a^2 - kab + b^2 - k = 0.$

By symmetry we may assume $a \geq b$. For all such pairs (a,b) of positive integers satisfying the equation, there is one $(a_0, b_0)$ such that $a_0$ is minimal. Let $f(x) = x^2 - kb_0x + b_0^2 - k$. We know that $a_0$ is one root of this quadratic, and the other is given by

$\displaystyle a_1 = kb_0 - a_0 = \frac{b_0^2 - k}{a_0}.\quad(1)$

From the first equation, $a_1$ is an integer.

a) If $a_1 < 0$,

$\displaystyle 0 = a_1^2 + b_0^2 - k(a_1b_0 + 1) > a_1^2 + b_0^2 > 0,$

a contradiction. Hence $a_1 \geq 0$.

b) Suppose $a_1 > 0$. Then $(a_1, b_0)$ satisfies the given equation and

$\displaystyle a_1 = \frac{b_0^2 - k}{a_0} \leq \frac{a_0^2 - k}{a_0} < a_0.$

However this contradicts the minimality assumption on $a_0$, so we conclude that $a_1 = 0$, and

$\displaystyle k = \frac{a_1^2 +b_0^2}{a_1b_0+1} = \frac{b_0^2}{1} = b_0^2,$

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 $kb-a \leq a$, so a smaller solution is obtained. This recurrence can be continued until we reach the minimal solution$(a_0, b_0)$. From the above argument, applying the recurrence one more time gives $(b_0,0)$. Then from the equation $kb_0 - a_0 = a_1 = 0$ we obtain $a_0 = b_0^3$. Reversing this recurrence gives us the solution $(ka-b,a) = (b_0^2a - b, a)$ from (a,b), leading to the general solution being adjacent terms $(x_{i+1}, x_i)$ of the sequence

$\displaystyle x_1, x_2, x_3, x_4, \ldots = b_0, b_0^3, b_0^5 - b_0, b_0^7 - 2b_0^3, \ldots$

where $x_{i+1} = b_0^2x_i - x_{i-1} = kx_i - x_{i-1}, b_0 \in \mathbb{N}$.

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 $a^2 + b^2 \geq 2ab > 2ab - 2$, so

$\displaystyle k = \frac{a^2 + b^2}{ab - 1} > 2.\quad...(2)$

We proceed as in the first problem. Assume a solution $a_0 > b_0$ with $a_0$ minimal (the case $a_0 = b_0$ can easily be shown to be impossible), then form the quadratic $f(x) = x^2 - kb_0x + b_0^2 + k$ and instead of (1), arrive at the second root

$\displaystyle a_1 = kb_0 - a_0 = \frac{b_0^2 + k}{a_0}.\quad...(3)$

By the minimality assumption $a_1 \geq a_0 > b_0$. Hence $b_0$ is less than the roots of a positive quadratic polynomial, so $f(b_0) > 0.$ Hence

$\displaystyle 0 < f(b_0) = b_0^2 - kb_0^2 + b_0^2 + k = (2-k)b_0^2 + k,$

from which

$\displaystyle b_0^2 < \frac{k}{k-2} < 4,$

where the second inequality follows from (2). As $b_0 \in \mathbb{N}$ and $b_0^2 < 4$, we must have $b_0 = 1$. Hence

$\displaystyle k = \frac{a_0^2 + 1}{a_0 - 1} = a_0 + 1 + \frac{2}{a_0 - 1},$

from which $a_0 = 2$ or $a_0 = 3$ and in either case $k = 5$, 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 $x_{i+1} = 5x_i - x_{i-1}$, 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

$\displaystyle a^2 - kab + b^2 = n,$

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  $0 \leq n \leq k+1$, then there are solutions to $a^2 - kab + b^2 = n$, in integers a and b if and only if n is a perfect square.

To show this, if $a_0 > b_0 > 0$ is the solution with $a_0$ minimal, form $f(x) = x^2 - kb_0x + b_0^2 - n$, which has roots $a_0$ and $kb_0 - a_0 = (b_0^2 - n)/a_0$. By minimality, $kb_0 - a_0 \leq 0 < a_0$. The quadratic f(x) is decreasing for $x < kb_0/2$, and so if $kb_0 - a_0 < 0$,

$\displaystyle 0 = f(kb_0 - a_0) \geq f(-1) = 1 + kb_0 + b_0^2 - n > 1 + k - j \geq 0.$

From this contradiction, we conclude that $kb_0 - a_0 = 0$, leading to $b_0^2 - n =0$, so n is a perfect square. Conversely, if $n = c^2$, 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, $f(b_0) > 0$, which leads to

$\displaystyle (k-2)b_0^2 < -n.$

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