Proving the converse of an IMO problem: are there infinitely many pairs of positive integers (m,n) such that m divides n^2 + 1 and n divides m^2 + 1?

Question

This problem is taken from the movie X+Y (A Brilliant Young Mind in the US). Apparently, it is a real problem from a British IMO qualifying exam:

Are there infinitely pairs of positive integers $(m,n)$ such that $m$ divides $n^2 + 1$ and $n$ divides $m^2 + 1$?

The answer is yes, with infinitely many solutions coming from alternating Fibonacci numbers:

Let $F_0 = 1$. Then $(F_{2n}, F_{2n+2})$ form a solution pair.

Besides the trivial solution $(1,1)$, all other solutions appear to be a pair of Fibonacci numbers of the above form. So I have been trying to prove this:

The only pairs of positive integers $(m,n)$ that satisfy $m|n^2+1$ and $n|m^2+1$ are $(1,1)$ and $(F_{2n}, F_{2n+2})$ for nonnegative $n$ where $F_{n}$ denotes the $nth$ Fibonacci number beginning with $F_0=1$.

Little success so far. Can anyone point me in the right direction? All I have so far is in suspecting that Vieta jumping might come in handy.

Answer 1

Will Jagy's approach essentially leads to the proof. I will supplement the remaining steps.

It is easy to see that the only solution $(m, n)$ with $m = n$ is $(1, 1)$, so we may assume WLOG $m < n$. As Will Jagy's calculations show, every solution $(m, n)$ with $m < n$ yields another solution $(v, m) = \left(\frac{m^2 + 1}{n}, m\right)$. Also, from this solution you can get back to the original solution $(m, n) = \left(m, \frac{m^2 + 1}{v}\right)$.

Now since $m > n$ we get $m^2 + 1 = nv > mv$, which implies $m^2 \ge mv$, i.e. $v \le m$. The case $v = m$ can only occur if $m^2 + 1 = mn$, i.e. $m(m - n) = -1$, which has only the two integer solutions $m = -1, n = -2$ and $m = 1, n = 2$.

This means: If we have a solution $(m, n)$ with $1 < m < n$, we can find a strictly smaller (in the coordiante-wise sense) solution $(v, m)$. This process can be repeated until we reach the pair $(1, 2)$.

It remains to prove that on the way back, i.e. $(v, m) \mapsto \left(m, \frac{m^2 + 1}{v}\right)$, we only get pairs of Fibonacci-numbers. If we assume $v = F_{2n + 1}$ and $m = F_{2n + 3}$, we need to verify that $n = \frac{m^2 + 1}{v} = F_{2n + 5}$, or equivalently $$F_{2n + 5}F_{2n + 1} = F_{2n + 3}^2 + 1.$$ This identity is known as Catalan's identity, which proves that all positive integer solutions are of the form $(1, 1)$, $(F_{2n + 1}, F_{2n + 3})$, or $(F_{2n + 3}, F_{2n + 1})$.

Remark: I assume that the Fibonacci numbers start with $F_0 = 0$, $F_1 = 1$, since this is the common definition in mathematics.

Answer 2

This is a beginning; i show how, given $m <n,$ we can find a smaller solution $v < m$ with a repeated element $m.$ A full proof would be not too much more, showing there is only one alternative smaller than $m$ that preserves $m,$ and there is only one alternative $w > n$ such that $w,n$ is a solution.

Anyway, $$ m^2 + 1 = nv, $$ $$ n^2 + 1 = m u.$$

We see that $v| (m^2 + 1).$ Now we want $m$ to divide $v^2 + 1.$ But $\gcd(m,n)=1.$ $$ n^2 v^2 + n^2 = m^4 + 2 m^2 + 1 + n^2,$$ $$ n^2 (v^2 + 1) = m^4 + 2 m^2 + mu, $$ $$ n^2 (v^2 + 1) = m \left( m^3 + 2 m + u \right). $$ $$ m | n^2 (v^2 + 1) \; \; \; \mbox{BUT} \; \; \; \gcd(m,n)=1. $$ $$ m | (v^2 + 1)$$

===============

Hmmmm. Well, so far we get three consecutive pairs in $$ v < m < n < u. $$ We get the desired result only if we can show uniqueness for $u,v,$ meaning that any solution $(t,m)$ with $t < m$ implies $t = v,$ and that any solution $(n,w)$ with $n < w$ implies $w = u.$ I'm not seeing it.