A IMO q6 but i changed it a bit

Suppose that $N \in \mathbb{N}$ is such that there exist $x,y \in \mathbb{N}$ such that $\frac{x^2 + y^2}{1 + xy} \; = \; N \hspace{5cm} (*)$ If $x=y$ then $N=1$ . Suppose that $N > 1$ , so that $x \neq y$ . Suppose for definiteness that $x > y$ . Then $x$ is a solution of the quadratic $X^2 - NyX + (y^2 - N) \; = \; 0$ and the other solution $z = Ny - x$ is an integer such that $y > z$ (since $xz < y^2$ and $x > y$ ) and $\frac{y^2 + z^2}{1 + yz} \; = \; N$ If $z < 0$ then $1 + yz \le 0$ , which means that $N$ is either infinite or negative. Thus we deduce that $z \ge 0$ .

If $z > 0$ then we can repeat the process, coming up with another solution $(z,w)$ of $(*)$ with $z > w \ge 0$ . By induction, we can find a sequence of integers $n_1,n_2,...,n_K,n_{K+1}$ defined by $n_1 \; = \; x \hspace{1cm} n_2 \; = \; y \hspace{2cm} n_{k+1} \; = \; Nn_k - n_{k-1} \hspace{0.5cm} 2 \le k \le N$ where $n_1 > n_2 > \cdots > n_K > n_{K+1} = 0$ (the sequence must terminate) such that $\frac{n_k^2 + n_{k+1}^2}{1 + n_kn_{k+1}} \; = \; N \hspace{2cm} 1 \le k \le K$ Putting $k = K$ in this last identity we see that $N = n_K^2$ is a perfect square.

Thus $\frac{x^2 + y^2}{1 + xy}$ is a perfect square whenever it is an integer, and hence cannot be prime.