How to solve these two simultaneous "divisibilities" : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Question

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ?

I succeed to prove there is an infinite number of solutions, but I cannot progress anymore.

Thanks !

Answer 1

It is convenient to introduce $x:=m+1$ and $y:=n+1$. Then $$ \begin{cases} x\ |\ y^2 - 2y + 2,\\ y\ |\ x^2 - 2x + 2. \end{cases} $$ It follows that $\gcd(x,y)\mid 2$, and thus there are two cases to consider:

---

Case $\gcd(x,y)=1$. We have $$xy\ |\ x^2 + y^2 - 2x - 2y + 2.$$

This is solved via Vieta jumping. Namely, one can show that $\frac{x^2 + y^2 - 2x - 2y + 2}{xy}\in\{ 0, -4, 8 \}$. The value $0$ corresponds to an isolated solution $x=y=1$, while each of the other two produces an infinite series of solutions, where $x,y$ represent consecutive terms of the following linear recurrence sequences: $$1,\ -1,\ 5,\ -17,\ 65,\ \dots \qquad(s_k=-4s_{k-1}-s_{k-2}+2)$$ and $$-1, -1, -5, -37, -289,\ \dots, \qquad(s_k=8s_{k-1}-s_{k-2}+2).$$

However, there are no entirely positive solutions here.

---

Case $\gcd(x,y)=2$. Letting $x:=2u$ and $y:=2v$ with $\gcd(u,v)=1$, we similarly get $$ \begin{cases} u\ |\ 2v^2 - 2v + 1,\\ v\ |\ 2u^2 - 2u + 1. \end{cases} $$ Unfortunately, Vieta jumping is not applicable here. Still, if we fix $$k:=\frac{2u^2 + 2v^2 - 2u - 2v + 1}{uv},$$ then the problem reduces to the following Pell-Fermat equation: $$((k^2-16)v + 2k+8)^2 - (k^2-16)(4u - kv - 2)^2 = 8k(k+4).$$

Example. Value $k=9$ gives $$z^2 - 65t^2 = 936.$$ with $z:=65v + 26$ and $t:=4u - 9v - 2$. It has two series of integer solutions in $z,t$: $$\begin{bmatrix} z_\ell\\ t_\ell\end{bmatrix} = \begin{bmatrix} 129 & -1040\\ -16 & 129\end{bmatrix}^\ell \begin{bmatrix} z_0\\ t_0\end{bmatrix}$$ with initial values $(z_0,t_0) \in \{(39,-3),\ (-1911,237)\}$.

Not every value of $(z_\ell, t_\ell)$ corresponds to integer $u,v$. Since the corresponding matrix has determinant 260, we need to consider sequences $(z_\ell, t_\ell)$ modulo 260. It can be verified that only first sequence produces integer $u,v$ and only for odd $\ell$, that is \begin{split} \begin{bmatrix} v_s\\ u_s\end{bmatrix} &= \begin{bmatrix} 65 & 0\\ -9 & 4\end{bmatrix}^{-1}\left(\begin{bmatrix} 129 & -1040\\ -16 & 129\end{bmatrix}^{2s+1} \begin{bmatrix} 39\\ -3\end{bmatrix} + \begin{bmatrix} -26\\ 2\end{bmatrix}\right)\\ &=\begin{bmatrix} 70433 & -16512\\ 16512 & -3871\end{bmatrix}^s \begin{bmatrix} 627/5 \\ 147/5\end{bmatrix} - \begin{bmatrix} 2/5 \\ 2/5\end{bmatrix} \end{split} or in a recurrence form: \begin{cases} v_s = 70433\cdot v_{s-1} -16512\cdot u_{s-1} + 21568,\\ u_s = 16512\cdot v_{s-1} -3871\cdot u_{s-1} + 5056, \end{cases} with the initial value $(v_0,u_0) = (125, 29)$. The next couple of values is $(8346845, 1956797)$ and $(555582723389, 130248348509)$, and it can be seen that the sequence grows quite fast.

UPDATE. Series of positive solutions exist for $$k\in \{9, 13, 85, 97, 145, 153, 265, 289, 369, \dots\}.$$ Most likely, this set is infinite, but I do not know how to prove this.