# Show that exist infinitely many pairs of natural numbers $(m, n)$ such that $\text{gcd}(m^2+1, n^2+1)=m+n$.

Show that exist infinitely many pairs of natural numbers $(m, n)$ such that $gcd(m^2+1, n^2+1)=m+n$.

I know solution $m=a, n=a^2-a+1$ ($n$ and $m$ are just given by simple polynomials, it is easy to see that they are satysfaying given conditions), but I know also that there exists another one, linked with identity involving Fibonacci numbers: $F_{n-1} * F_{n+1} - F_{n}^2 = (-1)^n$ (for $F_{0}=0$). It seems that this problem is extremely similar to one linked by user umpub here: 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?

Unfortunately, I can't find the answer. Can anyone present solution to my question or IMO problem linked by umpub?

## 1 Answer

If $F_n$ denotes the $n$-th Fibonacci number (where $F_0=F_1=1$), then $(m,n) = (F_{2k},F_{2k+1})$ is a solution for all $k \geq 0$.