Saudi Arabia Mathematical Competitions 2012

Since $a$ divides $n$ divides $a^2+b^2+1$, it follows that $a\mid b^2+1$. Similarly $b\mid a^2+1$. Thus we have $\gcd (a,b)=1$. We have $ab\mid a^2+b^2+1$. By symmetry, we can assume $a\le b$. It follows that $$a^2+b^2+1=kab(1)$$ for some positive integer $k$. In the case $a=b$ we have $2a^2+1$ is a multiple of $a$, meaning $a=1$. Consequently, $(a,b)=(1,1)$ and $k=3$.

Assume now $a>b$. The equation (1) considered as a quadratic equation in $a$ has a positive integer solution. Its second solution is $$a^{\prime }=kb-a=\frac{b^2+1}{a},$$ and it is also a positive integer. Moreover, $$a^{\prime }=\frac{b^2+1}{a}\le \frac{b^2+1}{b+1}\le b<a.$$ Thus, if equation (1) has a solution $(a,b)$ with $a>b$, then it also has another solution $(b,a^{\prime })$ with a strictly smaller sum of numbers. Applying the same argument to this new solution, then to the next solution, etc., we eventually arrive at a pair $(a_0,b_0)$ that cannot be further reduced. Hence, $$a_0=b_0=1,$$ and thus $k=3$. Thus, starting with an arbitrary solution one can descend to the pair $(1,1)$. Therefore, all possible solution $(a,b)$ of (1) are constructed in the infinite chain $$(1,1)\to (2,1)\to (5,2)\to (13,5)\to (34,13)\to \dots$$ The transfer to the next pair is by the rule $(x,y)\to (3x-y,x)$. It can easily be observed and then proved by induction that the $k^{\text{th}}$ pair, if the pair $(1,1)$ has number 0, consists of numbers $(F_{2k+1},F_{2k-1})$, where $(F_i{)}_{i\ge 0}$ is the Fibonacci sequence, $F_0=0$, $F_1=1$, and $F_{i+2}=F_{i+1}+F_i$, $i=0,1,\dots$. Finally, since $n$ is a multiple of $ab$ and is a divisor of $3ab$, it follows that either $$n=ab\text{ or }n=3ab.$$ Thus, the solutions are $$n=1,3,n=F_{2k-1}{F}_{2k+1},n=3F_{2k-1}{F}_{2k+1},k=1,2,\dots$$