IMO 2024 · Problem 2

Determine all pairs \((a,b)\) of positive integers for which there exist positive integers \(g\) and \(N\) such that \[ \gcd(a^n+b,\ b^n+a)=g \] holds for all integers \(n\geq N\). (Note that \(\gcd(x,y)\) denotes the greatest common divisor of integers \(x\) and \(y\).)

Official text of the problem. Official problem paper (PDF)

Answer

The only pair is \[ \boxed{(a,b)=(1,1)}. \]

Solution

Suppose that \((a,b)\) satisfies the condition, with fixed positive integers \(g\) and \(N\). Set \[ d=ab+1. \] Since \(\gcd(a,d)=\gcd(b,d)=1\), Euler’s theorem gives \[ a^{\varphi(d)}\equiv b^{\varphi(d)}\equiv1\pmod d, \] where \(\varphi\) is Euler’s totient function. Choose a positive multiple \(t\) of \(\varphi(d)\) such that \(t-1\geq N\). Thus \[ a^t\equiv b^t\equiv1\pmod d. \]

As \(ab\equiv-1\pmod d\), we have \[ a(a^{t-1}+b)=a^t+ab\equiv0\pmod d, \] and \[ b(b^{t-1}+a)=b^t+ab\equiv0\pmod d. \] We may cancel \(a\) and \(b\), respectively, because both are coprime to \(d\). Consequently, \[ d\mid\gcd(a^{t-1}+b,\ b^{t-1}+a)=g. \]

The hypothesis also applies at \(n=t\), so \(g\) divides both \(a^t+b\) and \(b^t+a\). Therefore \(d\) divides both of these numbers. Reducing modulo \(d\) gives \[ d\mid b+1 \qquad\text{and}\qquad d\mid a+1. \] All these numbers are positive, so \[ ab+1\leq b+1 \qquad\text{and}\qquad ab+1\leq a+1. \] The first inequality implies \(a\leq1\), and the second implies \(b\leq1\). Since \(a,b\) are positive integers, \(a=b=1\).

Conversely, for \((a,b)=(1,1)\), \[ \gcd(1^n+1,\ 1^n+1)=2 \] for every positive integer \(n\). Hence this pair satisfies the condition with \(g=2\) and \(N=1\).

The solution was checked against the official IMO shortlist solutions.