The last condition confuses me If we have infinite pairs $ (x,y)$, then we simply make $ x$ and $ y$ negative so that $ x + y\le m + 1$. (I assume $ x$ and $ y$ are allowed to be negative, as otherwise we couldn't possibly have infinite pairs with that condition?) Anyway, just using conditions (i), (ii), and (iii),

I claim that there exist infinitely many integers such that $x \mid y^2+m$ and $y \mid x^2+m.$ Indeed, if $(x,y)$ works, so does $(x, kx-y),$ where $k=m+2.$ Starting from the initial pair $(1,1),$ this generates infinitely many such coprime integers because $\gcd (kx-y, x)=1$ whenever $\gcd (x, y) = 1.$

AnonymousBunny wrote: I claim that there exist infinitely many integers such that $x \mid y^2+m$ and $y \mid x^2+m.$ Indeed, if $(x,y)$ works, so does $(x, kx-y),$ where $k=m+2.$ Starting from the initial pair $(1,1),$ this generates infinitely many such coprime integers because $\gcd (kx-y, x)=1$ whenever $\gcd (x, y) = 1.$ For any future visitor—this is just flat out wrong. A counterexample is $(1, 2)$ with $m=3$. $(2,9)$ doesn't work for obvious reasons. Counterexamples exist whenever $m + 1$ is not prime. I have no idea why this post has three upvotes lol

Let $a_n=(m+2)a_{n-1}-a_{n-2}$ and $a_0=a_1=1$ Note that $\boxed{x=-a_k, y=-a_{k+1}}$ works for all positive integers $k$. Proof: (i) $\gcd(x,y)=\gcd(a_k,a_{k+1})=\gcd(a_k,(m+2)a_k-a_{k-1})=\gcd(a_k,a_{k-1})=...=\gcd(a_0,a_1)=1$ (ii) Prove that $a_{k+1}a_{k-1}=a_k^2+m$ through induction Base case: when $k=2$, $a_2a_0=a_2=(m+1)1-1 =m+1=a_1^2+m$. Inductive step: Assume that $k$ works. Then $a_{k+2}a_k=(m+2)a_{k+1}a_k-a_k^2=(m+2)a_{k+1}a_k-(a_{k+1}a_{k-1}-m)=a_{k+1}((m+2)a_k-a_{k-1})+m=a_{k+1}^2+m$. As a result, $a_{k+1}$ divides $a_k^2+m$, and $y$ divides $x^2+m$. (iii) Note that the remainder when $y$ is divided by $x$ is equal to $-a_{k-1}$ due to the recursive formula. As a result, $y^2+m \equiv a_{k-1}^2+m \pmod x$. From (ii), get that this divides $x$. As a result, $x$ divides $y^2+m$. (iv) Prove that all of $a_k > 0$ and that $a_k$ is increasing (besides $a_0$ and $a_1$) through induction. Base case: $0<a_1<a_2$, since $a_2=(m+2)a_1-a_0=(m+1)a_1>a_1$. Inductive step: $a_n=(m+2)a_{n-1}-a_{n -2}>a_{n+1}+a_{n-1}-a_{n-2}>a_{n-1}$, so this is increasing after the first two values Since $a_k$ is increasing, all the terms are positive, since the first term is positive. As a result, $x$ and $y$ are both negative, and $m+1$ is positive, so $x+y \le m+1$