2024 IMO Problems/Problem 2: Difference between revisions

Revision as of 22:08, 12 March 2025

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

@@ Line 2: / Line 2: @@
 <cmath>\gcd (a^n+b,b^n+a)=g</cmath>
 holds for all integer <math>n\ge N</math>.
+==Solution 1==
+We will determine all pairs <math>(a,b)</math> of positive integers such that <math>\gcd(a^n+b,b^n+a)=g</math> for all <math>n \geq N</math>.
+First, <math>(1,1)</math> works with <math>g=2</math>. Now for any solution <math>(a,b)</math>:
+\begin{lemma}
+<math>g = \gcd(a,b)</math> or <math>g = 2\gcd(a,b)</math>.
+\end{lemma}
+\begin{proof}
+Since <math>g</math> divides both <math>a^N+b</math> and <math>a^{N+1}+b</math>, it divides their difference <math>a^N(a-1)</math>. Similarly, <math>g</math> divides <math>b^N(b-1)</math>. Thus <math>g</math> divides <math>a-b</math>, so <math>g</math> divides <math>a^N+b-(a-b)=a^N+a</math>. Hence <math>g</math> divides <math>\gcd(a^N+a,a)=\gcd(a,a-1)=1</math>, a contradiction unless <math>g</math> divides both <math>a</math> and <math>b</math>.
+\end{proof}
+Let <math>d=\gcd(a,b)</math> and write <math>a=dx</math>, <math>b=dy</math> with <math>\gcd(x,y)=1</math>. Then
+<cmath>\gcd(a^n+b,b^n+a) = d \cdot \gcd(d^{n-1}x^n+y, d^{n-1}y^n+x)</cmath>
+Using Euler's theorem, for <math>n \equiv -1 \pmod{\varphi(K)}</math> where <math>K=d^2xy+1</math>, we have:
+<cmath>d^{n-1}x^n+y \equiv d^{-2}x^{-1}+y \equiv d^{-2}x^{-1}(1+d^2xy) \equiv 0 \pmod{K}</cmath>
+Similarly, <math>d^{n-1}y^n+x \equiv 0 \pmod{K}</math>. Since these are divisible by <math>K</math>, and <math>K</math> must divide <math>g \leq 2d</math>, we must have <math>d=x=y=1</math>, giving <math>(a,b)=(1,1)</math>.
+~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

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: Difference between revisions

Revision as of 22:08, 12 March 2025

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