Saudi Arabian Mathematical Competitions

Suppose by contrary that one of $a, b$ is even, say $a$. So $a^{2}+1$ is odd. This means that $b+1$ must be odd, or equivalently, $b$ is even. We will prove that this cannot happen.

Indeed, put $d=\gcd(a+1, b+1)$ then $d \mid a+1 \mid b^{2}+1$, hence $d \mid b^{2}-b = b(b+1) + 2b$. From this, we have $d \mid 2b$ and $d \mid 2(b+1) = 2b+2$ so $d \mid 2$. But $a+1, b+1$ are odd numbers so $d$ odd, which gives $d=1$.

On the other hand, by assumption $a+1 \mid a^{2}+b^{2}$, $b+1 \mid a^{2}+b^{2}$, we get $a^{2}+b^{2} = (a^{2}+1) + (b^{2}-1) = (a^{2}-1) + (b^{2}+1)$ is divisible by both $a+1$ and $b+1$. Therefore $(a+1)(b+1) \mid a^{2}+b^{2}$ (since $a+1$ and $b+1$ are coprime).

In other words, there exists a positive integer $k$ such that
$$a^{2}+b^{2}=k(a+1)(b+1) .$$
We now prove that this equation has no integer solution. Fix a value of $n$, assume that this equation has a solution of positive integers. We can choose positive integers $x_{0}, y_{0}$ satisfying the equation with the property that the sum $x_{0}+y_{0}$ is smallest and $x_{0} \geq y_{0}$.

Consider the quadratic equation
$$X^{2}-X \cdot n(y_{0}+1)+y_{0}^{2}-n y_{0}-n=0 .\quad (*)$$
This equation has a solution $x_{0}$ so it also has another solution, say $x_{1}$. From Vieta's theorem, we have
$$x_{0}+x_{1}=n(y_{0}+1), \quad x_{0} x_{1}=y_{0}^{2}-n y_{0}-n$$
We consider the following cases:

1. If $x_{1}<0$, i.e. $x_{1} \leq -1$, then from $(*)$ we see that $x_{1}^{2}-x_{1} \cdot n(y_{0}+1)+ y_{0}^{2}-n y_{0}-n=0$ or
$$0 \geq x_{1}^{2}+n(y_{0}+1)+y_{0}^{2}-n y_{0}-n = x_{1}^{2}+y_{0}^{2}>0,$$
which is clearly a contradiction.

2. If $x_{1}>0$ then $(x_{1}, y_{0})$ is also another solution of $(*)$, from the choice of $x_{0}$, we have $x_{1}>x_{0}$. Moreover, since $x_{0} x_{1}=y_{0}^{2}-n y_{0}-n$ it follows that $x_{0}^{2}<x_{0} x_{1}=y_{0}^{2}-n y_{0}-n<y_{0}^{2}$, this is also a contradiction because of the inequality $x_{0} \geq y_{0}$.

Hence, $x_{1}=0$, and in this case $y_{0}^{2}=n(y_{0}+1)$, which implies that $y_{0}+1 \mid y_{0}^{2}$. This cannot hold for $y_{0} \geq 2$.

Therefore, we conclude that $a, b$ are odd numbers, this ends the proof.