# IMO 1988, problem 6

In 1988, IMO presented a problem, to prove that $k$ must be a square if $a^2+b^2=k(1+ab)$, for positive integers $a$, $b$ and $k$. I am wondering about the solutions, not obvious from the proof. Beside the trivial solutions a or $b=0$ or 1 with $k=0$ or $1$, an obvious solution is $a=b^3$ so that the equation becomes $b^6+b^2=b^2(1+b^4)$ . Are there any other solutions?

• There are some very detailed analyses of this problem here searchable with the words 'IMO 1988'.
– zyx
Sep 4, 2013 at 7:48
• mathoverflow.net/questions/250172/… May 12, 2017 at 4:40

This is a famous problem, here is one of the solutions that I like the most that I read it in a book previously, but later in a topic on here I realized the importance of the problem (The credit goes to T. Andreescu & R. Gelca If I remember it correctly, but I'm not sure, since 11 individuals in that year solved this problem and I'm not sure about their solutions):

Solution: Suppose that $\displaystyle \frac{a^2+b^2}{a.b+1}=x$ We want to prove that for every non-negative integer pairs $(\alpha,\beta)$ with the property that $\displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}=x$ and $\alpha \geq \beta$ the pair that minimizes $\alpha+\beta$ must imply $\beta=0$. If that happened, then $x=\alpha^2$. So, suppose that $(\alpha,\beta)$ is such a pair that minimizes $\alpha+\beta$ but $\beta>0$. then we can obtain the equation $y^2 - \beta xy + \beta^2 -x =0$ from $\displaystyle \frac{y^2+\beta^2}{y\beta+1}=x$. This equation has $\alpha$ as one of its roots and since the sum of the roots is $\beta x$, the other root must be $\beta x - \alpha$. Now if we prove that $0 \leq \beta x - \alpha < \alpha$ then we're done because this contradicts the minimality of $(\alpha,\beta)$

$x = \displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}<\frac{2\alpha^2}{\alpha \beta} = \frac{2 \alpha}{\beta} \implies \beta x-\alpha < \alpha$

and it's also possible to show that $\beta.x - \alpha \geq 0$ but honestly I don't remember that part of the proof and I leave it to you. That completes the proof.

(Also check that wikipedia link provided by pre-kidney).

• The question does not ask for a proof, it asks for the listing of the solutions of the equation in $k$, $a$ and $b$. Dec 27, 2022 at 15:36

The technique for this type of problem is called "Vieta root jumping". On the wikipedia page describing this technique, this very problem is used as an example. See here.

Of course there are many more solutions; we can enumerate them by flipping repeatedly and using symmetry. For example, your solution $(b, b^3)$ is the result of flipping $(b,0)$ when $k=b^2$. But if we flip around $b^3$ instead, we get the new solution $(b^5-b, b^3)$.

Indeed, $$x^2-b^5x+(b^6-b^2)=(x-b)(x-b^5+b)$$ so we also have $$b^6 + (b^5-b)^2 = b^2(1 + b^3(b^5-b))$$

All solutions can be written as: $$\text{if n is even:}\enspace a_n= { \sum\limits_{i=0}^{{n\over{2}}} {(-1)^{i+{n\over{2}}}{{n\over{2}}+i\choose {n\over{2}}-i}g^{4i+1}}} \\ \text{if n is odd:}\enspace a_n= \sum\limits_{i=0}^{{n-1\over{2}}} (-1)^{i+{n-1\over{2}}}{1+{n-1\over{2}}+i \choose {n-1\over{2}}-i}g^{4i+3} \implies \\ {{a_n}^2+{a_{n+1}}^2\over{a_na_{n+1}+1}}=g^2\\$$ Or also: $$a_n={g{\bigg({g^2+\sqrt{g^4-4}\over{2}}\bigg)}^n\over{\sqrt{g^4-4}}} - {g{\bigg({g^2-\sqrt{g^4-4}\over{2}} \bigg)}^n\over{\sqrt{g^4-4}}} \\$$

see here for complete solution

Not quite a proof to the original IMO problem, but there definately is a very easy way to compute all possible answers. Also it demonstrates that here, Vieta jumping is basically just using symmetry to jump between the two solutions of the good old quadratic formula.

Nothing complicated below, but I haven't seen this explanation anywhere else.

Suppose: $${{a^2+b^2} \over {1+ab}} = c$$ Then using the quadratic formula to solve b (and a little rewriting) gives: $$b = {ac \pm \sqrt {a^2 (c^2-4) + 4c} \over 2}$$ Using this we can compute all answers for any given c. Eg: assume c = 4. Then we get: $$b = {a \cdot 4 \pm \sqrt {a^2 \cdot 12 + 16} \over 2}$$ We know that a = 0 will always provide a solution. That gives us: $$a = 0 \Rightarrow b = {{0 \cdot 4\pm \sqrt {0 \cdot 12 + 16}} \over 2} = 2 \Rightarrow (a,b) = (0,2)$$ But because of the symmetry, if (0,2) is a solution, then (2,0) must also be a solution. And since the quadratic formula has 2 solutions, it will produce another solution. $$a = 2 \Rightarrow \space b = {{2 \cdot 4 \pm \sqrt {4 \cdot 12 + 16}} \over 2} = 0 \space or \space 8 \Rightarrow (a,b) = (2,8)$$ $$a = 8 \Rightarrow \space b = {{8 \cdot 4 \pm \sqrt {64 \cdot 12 + 16}} \over 2} = {32 \pm 28\over 2} = 2 \space or \space 30 \Rightarrow (a,b) = (8,30)$$ $$a = 30 \Rightarrow \space b = {{30 \cdot 4 \pm \sqrt {900 \cdot 12 + 16}} \over 2} = {120 \pm 104\over 2} = 8 \space or \space 112 \Rightarrow (a,b) = (30,112)$$ Same can be done for c = 9, 16, 25, etc.

Supposing that

$$\frac{a^2 + b^2}{ab + 1} = k$$ then

$$a^2 - a(kb) + (b^2 - k) = 0$$

So using quadratic formula gives: $$a = \frac{kb \pm \sqrt{k^2b^2 -4(b^2 -k)}}{2}$$

The solutions are when $k = b^2$ and thus $a= kb = b^3$

So $$b = 1 , a = 1 , k= 1$$ $$b = 2 , a = 8, k = 4$$

$$b= 3, a= 27, k = 9$$ and so on....

There are other ways of getting more solutions than these such as b = 8, a = 30 and k = 4 where k is not $b^2$ or $a = b^3$ and of course the zero one. I have not yet found a way to find more solutions than this.

• But what about for example $b=8,a=30,k=4$ ? Clearly we don't have : $k=b^2$ or $a=b^3$. But nevertheless we have : $\enspace \frac{8^2+30^2}{8.30+1}=4$.. Jun 30, 2017 at 12:42
• Oh yes, you are right. Thank you for that, I will look into this question more and will edit my answer. Jul 5, 2017 at 8:53

Let the following sequence of polynomials \begin{equation*} P_1(n)\,=\,n\,,\,\, P_2(n)\,=\,n^3,\ldots, P_{k+2}(n)\,=\,\frac{P^2_{k+1}(n)-n^2}{P_k(n)}, \,\,\,k\in\mathbb N, \end{equation*} which in fact have the following general formula $$P_m(n)\,=\,\sum_{r=0}^{\left[\frac{m-1}{2}\right]} (-1)^r\,\left( \begin{array}{c} \!m\!-\!r\!-\!1\! \\ r \end{array} \right) \,n^{2m-4r-1}. \label{polunomial}$$ Then one can show the following: If $a,b$ are positive integers with $b\ge a$, such that $$\frac{a^2+b^2}{1+ab}=k$$ is also an integer, then $k$ is a perfect square, i.e., $k=n^2$, and there exists an $m\in\mathbb N$, such that $$a=P_m(n)\quad\text{and}\quad b=P_{m+1}(n).$$

For given positive integers a and b, and applying simple division of $$(a^2 + b^2)$$ by $$(ab + 1)$$ we have quotient as a/b and remainder as $$(b^2 - a/b)$$.

For the result to be a perfect division, the remainder must be zero. Therefore $$(b^2 - a/b) = 0$$ which gives the relation $$a=b^3$$.

Applying $$a=b^3$$ in the equation $$x=(a^2 + b^2)/(ab + 1)$$, we have $$x=b^2$$ which is a perfect square of an integer.

All the number pairs $$(a,b)$$ of the form $$(b^3,b)$$ are solutions of the above equation and the number which is a perfect square is of the form $$x = b^2$$ applicable for all $$b$$ belonging to a set of positive integers.