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.


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.