2024 IMO Problems/Problem 2

Find all positive integer pairs $(a,b),$ such that there exists positive integer $g,N,$ \[\gcd (a^n+b,b^n+a)=g\] holds for all integer $n\ge N$.

Solution 1

We will determine all pairs $(a,b)$ of positive integers such that $\gcd(a^n+b,b^n+a)=g$ for all $n \geq N$.

First, $(1,1)$ works with $g=2$. Now for any solution $(a,b)$:

\begin{lemma} $g = \gcd(a,b)$ or $g = 2\gcd(a,b)$. \end{lemma}

\begin{proof} Since $g$ divides both $a^N+b$ and $a^{N+1}+b$, it divides their difference $a^N(a-1)$. Similarly, $g$ divides $b^N(b-1)$. Thus $g$ divides $a-b$, so $g$ divides $a^N+b-(a-b)=a^N+a$. Hence $g$ divides $\gcd(a^N+a,a)=\gcd(a,a-1)=1$, a contradiction unless $g$ divides both $a$ and $b$. \end{proof}

Let $d=\gcd(a,b)$ and write $a=dx$, $b=dy$ with $\gcd(x,y)=1$. Then \[\gcd(a^n+b,b^n+a) = d \cdot \gcd(d^{n-1}x^n+y, d^{n-1}y^n+x)\]

Using Euler's theorem, for $n \equiv -1 \pmod{\varphi(K)}$ where $K=d^2xy+1$, we have: \[d^{n-1}x^n+y \equiv d^{-2}x^{-1}+y \equiv d^{-2}x^{-1}(1+d^2xy) \equiv 0 \pmod{K}\]

Similarly, $d^{n-1}y^n+x \equiv 0 \pmod{K}$. Since these are divisible by $K$, and $K$ must divide $g \leq 2d$, we must have $d=x=y=1$, giving $(a,b)=(1,1)$.

~brandonyee

Video Solution

https://www.youtube.com/watch?v=VXFG1t_ksfI (including motivation to derive solution)

Video Solution(Fermat's little theorem,In English)

https://youtu.be/QTBcTtY46HI

Video Solution(Fermat's little theorem,In Chinese)

https://youtu.be/8WOff2j0giY

Video Solution

https://youtu.be/5SZUbbxoK1M

See Also

2024 IMO (Problems) • Resources
Preceded by
Problem 1
1 2 3 4 5 6 Followed by
Problem 3
All IMO Problems and Solutions