IMO2024 Shortlisted Problems

It is clear that we may take $g=2$ for $(a,b)=(1,1)$. Supposing that $(a,b)$ satisfies the conditions in the problem, let $N$ be a positive integer such that $\gcd \left(a^n+b,b^n+a\right)=g$ for all $n⩾N$.

Lemma. We have that $g=\gcd (a,b)$ or $g=2\gcd (a,b)$.

Proof. Note that both $a^N+b$ and $a^{N+1}+b$ are divisible by $g$. Hence $$a\left(a^N+b\right)-\left(a^{N+1}+b\right)=ab-b=a(b-1)$$ is divisible by $g$. Analogously, $b(a-1)$ is divisible by $g$. Their difference $a-b$ is then divisible by $g$, so $g$ also divides $a(b-1)+a(a-b)=a^2-a$. All powers of $a$ are then congruent modulo $g$, so $a+b\equiv a^N+b\equiv 0(\mathrm{mod}g)$. Then $2a=(a+b)+(a-b)$ and $2b=(a+b)-(a-b)$ are both divisible by $g$, so $g\mid 2\gcd (a,b)$. On the other hand, it is clear that $\gcd (a,b)\mid g$, thus proving the Lemma.

Let $d=\gcd (a,b)$, and write $a=dx$ and $b=dy$ for coprime positive integers $x$ and $y$. We have that $$\gcd \left((dx{)}^n+dy,(dy{)}^n+dx\right)=d\gcd \left(d^{n-1}{x}^n+y,d^{n-1}{y}^n+x\right),$$ so the Lemma tells us that $$\gcd \left(d^{n-1}{x}^n+y,d^{n-1}{y}^n+x\right)⩽2$$ for all $n⩾N$. Defining $K=d^{2}xy+1$, note that $K$ is coprime to each of $d,x$, and $y$. By Euler's theorem, for $n\equiv -1(\mathrm{mod}\phi (K))$ we have that $$d^{n-1}{x}^n+y\equiv d^{-2}{x}^{-1}+y\equiv d^{-2}{x}^{-1}\left(1+d^{2}xy\right)\equiv 0(\mathrm{mod}K),$$ so $K\mid d^{n-1}{x}^n+y$. Analogously, we have that $K\mid d^{n-1}{y}^n+x$. Taking such an $n$ which also satisfies $n⩾N$ gives us that $$K\mid \gcd \left(d^{n-1}{x}^n+y,d^{n-1}{y}^n+x\right)⩽2$$ This is only possible when $d=x=y=1$, which yields the only solution $(a,b)=(1,1)$.

For any prime factor $p$ of $ab+1,p$ is coprime to $a$ and $b$. Take an $n⩾N$ such that $n\equiv -1(\mathrm{mod}p-1)$. By Fermat's little theorem, we have that $$\begin{array}{rl}& a^n+b\equiv a^{-1}+b=a^{-1}(1+ab)\equiv 0(\mathrm{mod}p),\\ & b^n+a\equiv b^{-1}+a=b^{-1}(1+ab)\equiv 0(\mathrm{mod}p),\end{array}$$ then $p$ divides $g$. By the Lemma, we have that $p\mid 2\gcd (a,b)$, and thus $p=2$. Therefore, $ab+1$ is a power of 2, and $a$ and $b$ are both odd numbers.

If $(a,b)\ne (1,1)$, then $ab+1$ is divisible by 4, hence $\{a,b\}=\{-1,1\}(\mathrm{mod}4)$. For odd $n⩾N$, we have that $$a^n+b\equiv b^n+a\equiv (-1)+1=0(\mathrm{mod}4)$$ then $4\mid g$. But by the Lemma, we have that ${\nu }_2(g)⩽{\nu }_2(2\gcd (a,b))=1$, which is a contradiction. So the only solution to the problem is $(a,b)=(1,1)$.

---

Alternative solution.

After proving the Lemma, one can finish the solution as follows.

For any prime factor $p$ of $ab+1,p$ is coprime to $a$ and $b$. Take an $n⩾N$ such that $n\equiv -1(\mathrm{mod}p-1)$. By Fermat's little theorem, we have that $$\begin{array}{rl}& a^n+b\equiv a^{-1}+b=a^{-1}(1+ab)\equiv 0(\mathrm{mod}p),\\ & b^n+a\equiv b^{-1}+a=b^{-1}(1+ab)\equiv 0(\mathrm{mod}p),\end{array}$$ then $p$ divides $g$. By the Lemma, we have that $p\mid 2\gcd (a,b)$, and thus $p=2$. Therefore, $ab+1$ is a power of 2, and $a$ and $b$ are both odd numbers.

If $(a,b)\ne (1,1)$, then $ab+1$ is divisible by 4, hence $\{a,b\}=\{-1,1\}(\mathrm{mod}4)$. For odd $n⩾N$, we have that $$a^n+b\equiv b^n+a\equiv (-1)+1=0(\mathrm{mod}4)$$ then $4\mid g$. But by the Lemma, we have that ${\nu }_2(g)⩽{\nu }_2(2\gcd (a,b))=1$, which is a contradiction. So the only solution to the problem is $(a,b)=(1,1)$.