Art of Problem Solving
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

2024 IMO Problems/Problem 2: Difference between revisions

← Older edit
Quantumraven (talk | contribs)
editor
9 edits
Quantumraven (talk | contribs)
editor
9 edits
 
Line 8: Line 8:
First, <math>(1,1)</math> works with <math>g=2</math>. Now for any solution <math>(a,b)</math>:
First, <math>(1,1)</math> works with <math>g=2</math>. Now for any solution <math>(a,b)</math>:


/begin{lemma}
Lemma :
<math>g = \gcd(a,b)</math> or <math>g = 2\gcd(a,b)</math>.
<math>g = \gcd(a,b)</math> or <math>g = 2\gcd(a,b)</math>.
/end{lemma}


\begin{proof}
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>.
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
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

Latest revision as of 20:33, 5 September 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)$:

Lemma : $g = \gcd(a,b)$ or $g = 2\gcd(a,b)$.

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$.

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://wiki.aopstest.com/wiki/index.php?title=2024_IMO_Problems/Problem_2&oldid=259812"