First (m,n)=1, then the requirements are equivalent to mn divides m^2+n^2+1. We can prove m^2+n^2+1=3mn by classic infinite decent. That means starting from (1,1), we can get a new pair (m,3m-n) from (m,n) when m>=n.

we add $(m,n)=1$, we can get $mn \mid n^2+m^2+1$, then using Vieta Jump.

It is a well know problem... $mn|n^2+m^2+1 \implies n^2+m^2+1=kmn$, where $k \in N^{+}$.I claim that $k=3$. Suppose $(m,n)$ is a solution with $k \ne 3$. Then if $m=n$ then $2m^2+1=km^2$ leading to $k=3$ which is not possible.For $n \ne m$ we have $(mk-n)^2+m^2+1=(mk-n)mk$ which means $mk-n,m$ is also the solution. We can check that $mk-n <n$ and hence we have a decreasing sequence of positive integers which is a contradiction to FMID. SO we have $k=3$. For $k=3$ , $m^2+n^2+1=3mn$, $(1,1)$ is the solution of the equation. Note that if $x_{n+1},y_{n+1}$ is a solution of the above equation then $x_{n},3y_{n}-x_{n}$ is a solution also. So we have $x_{n+1}=3x_{n}-x_{n-1}, x_1=1, x_2=2$ which characterizes the Fibonacci sequence of odd index. Hence $(F_{2n+1},F_{2n-1})$ is the solution.