Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 IMO Problems/Problem 2"
(→‎Solution 1)
 
(5 intermediate revisions by 4 users not shown)
Line 2: Line 2:
 
<cmath>\gcd (a^n+b,b^n+a)=g</cmath>
 
<cmath>\gcd (a^n+b,b^n+a)=g</cmath>
 
holds for all integer <math>n\ge N</math>.
 
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==
 
==Video Solution==
 
https://www.youtube.com/watch?v=VXFG1t_ksfI (including motivation to derive 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==
 +
 +
{{IMO box|year=2024|num-b=1|num-a=3}}

Latest revision as of 23: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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_IMO_Problems/Problem_2&oldid=244873"