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

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

Page

Toolbox

Search

2024 IMO Problems/Problem 2

Contents

Solution 1

Video Solution

Video Solution（Fermat's little theorem，In English）

Video Solution（Fermat's little theorem，In Chinese）

Video Solution

See Also