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\ge y_0$.

Consider the quadratic equation $$X^2-X\cdot n(y_0+1)+y_0^2-n{y}_0-n=0.(\ast )$$ 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),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\le -1$, then from $(\ast )$ we see that $x_1^2-x_1\cdot n(y_0+1)+y_0^2-n{y}_0-n=0$ or $$0\ge 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 $(\ast )$, 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\ge 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\ge 2$.

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