41st Balkan Mathematical Olympiad

Let $a+1=A^2$, $b+1=B^2$ where $1<A<B$ are positive integers. We prove the result by induction on $\max \{a,b\}=b$. Define $C:=AB-\sqrt{ab}=AB-\sqrt{(A^2-1)(B^2-1)}$ which is an integer as $ab$ is a perfect square. Define $c:=C^2-1$. We will now prove the following: $1<c<b$ $ac$ is a perfect square (noting that it follows immediately from the construction that $a+1,c+1$ are perfect squares.) * $\text{gcd}(a,c)=\text{gcd}(a,b)$ We will then be done by induction as by repeatedly applying this process, we preserve the $\text{gcd}$ and must eventually reach a case with $a=b$ which we have proved above. For the first part, $$C=AB-\sqrt{A^2{B}^2-A^2-B^2+1}>AB-\sqrt{A^2{B}^2-2AB+1}=1$$ where the inequality is strict since $A\ne B$. Furthermore, $$2(A-1)B^2\ge 2B^2>A^2-1⟹A^2+B^2-1<2A{B}^2-B^2$$ leading to $$C=AB-\sqrt{A^2{B}^2-A^2-B^2+1}<AB-\sqrt{A^2{B}^2-2A{B}^2+B^2}=B.$$ So $1<C<B$ and therefore $1<c<b$.

For the second part, expanding the definition of $C$ we get: $$(AB-C{)}^2=(A^2-1)(B^2-1)⟹A^2+B^2+C^2=2ABC+1(1)$$ We can rearrange this to: $$ac=(A^2-1)(C^2-1)=(B-AC{)}^2(2)$$ which shows $ac$ is a perfect square. For the final part, note that if $d\mid A^2-1$ and $d\mid C^2-1$ then from (2), $d\mid B-AC$. Then from (1) we have: $$B^2-1=2ABC-A^2-C^2\equiv 2A^2{C}^2-A^2-C^2\equiv 2-1-1\equiv 0(\mathrm{mod}d)$$ Thus $d\mid B^2-1$. Setting $d=\gcd (a,c)$, we see that $\gcd (a,c)\mid \gcd (a,b)$. But the condition we're using in (1) is symmetric in $A,B,C$ and so in a similar way we get $\gcd (a,b)\mid \gcd (a,c)$. Combining, we must have $\gcd (a,b)=\gcd (a,c)$.

---

Alternative solution.

Using the notation from the solution above, define $g:=\gcd (a,b)$ then, as $ab$ is a perfect square, there exists positive integers $x,y$ with $\gcd (x,y)=1$ such that: $$a=A^2-1=g{x}^2\text{and}b=B^2-1=g{y}^2$$ Then the pairs $(A,x)$ and $(B,y)$ satisfy the Pell equation: $$p^2-g{q}^2=1$$ If $(p_1,q_1)$ is the fundamental solution to this equation, then all other solutions are generated from the recurrences: $$p_{n+1}=p_1{p}_n+g{q}_1{q}_n$$ $$q_{n+1}=p_1{q}_n+q_1{p}_n$$ and in particular, $q_1|q_n$ for all $n$. Thus $q_1|x,y$ and hence $q_1|\gcd (x,y)=1$ so $q_1=1$. But then, considering the fundamental solution: $$1=p_1^2-g{q}_1^2=p_1^2-g⟹g+1=p_1^2$$ as required.