Chaitanya's Random Pages

June 27, 2011

Interesting quadratic diophantine equations

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.

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

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

Create a free website or blog at WordPress.com.

%d bloggers like this: