The famous "hardest" problem of IMO: If positive integers $a,b$ are such that
$$\frac{a^2 + b^2}{1 + ab} = k$$
and $k$ is a positive integer, then $k$ must be a perfect square.
In this post we will allow $a,b$ to be integers (while keeping $k > 0$), and also try to characterize the solution set when $k$ is a perfect square.
.
.
.
.
.
First we start of with a useful observation.
$\textbf{Observation:}$ Any solution $(a,b)$ satisfies $ab \geq 0$.
$\textbf{Proof:}$ We must have $1 + ab = \frac{a^2 + b^2}{k} > 0$ and thus $ab \geq 0$.
Now because the quadratic in a
$$a^2 - (kb) a + (b^2 - k) = 0$$
has sum of roots $kb$, if $(a_0, b)$ is a solution, then so is $(kb - a_0, b)$. Similary treating it as a quadratic in $b$, if $(a, b_0)$ is a solution and thus so is $(a, ka - b_0)$.
Thus if $(a,b)$ is a solution, then so are $(a, ka -b) = (a,x)$ and $(kb - a, b) = (y,b)$. Call these the companion solutions of $(a,b)$
Also observe that from both $(a,x)$ and $(y,b)$ we get back $(a,b)$ as one of the companion solutions.
Now $bx = (ka - b)b = a^2 -k$ and $ay = (kb-a)a = b^2 -k$.
Thus $axby = (a^2 - k)(b^2 - k)$. If $ab > 0$, then we must have $axby < a^2b^2$.
Thus at-least one of $ax$ or $by$ is a non-negative integer $< ab$
Thus if we have a solution $(a,b)$ with $ab > 0$, one of its companion solution has a lower value of the product $ab$.
Since $ab \geq 0$, we must ultimately have that $xy = 0$ (say $y = 0$) for some solution $(x,y)$, and thus $k = \frac{x^2 + 0}{1 + x\times0} = x^2$ and so $k$ must be a perfect square (and this completes the proof for the IMO problem).
$\textbf{Characterization of the solutions}:$
Say $k = m^2$.
Now observe that, what we showed that, if $(a,b)$ is any solution with $ab > 0$, then there is a sequence of companions leading to the $(0, m)$ solution. We also noted that this is a reversible step, and thus any solution can be obtained by starting with $(0, m)$ and taking the companions.
Thus we could characterize solutions as a sequence of companions.
$$(a_{n+1}, b_{n+1}) = (k a_n - b_n, a_n)$$
Starting with $(a_0, b_0) = (m, 0)$
This can be written as a linear recurrence (with characteristic equation $x^2 -kx + 1 = 0$) or we can use matrix multiplication (applying diagonalization) etc and we can easily give a closed form formula, which we will omit the details.
The negative integer solutions are easily dealt with because we always have $ab \geq 0$ and thus we can negate the solutions in which both $a,b$ are non-negative.