docu International Mathematical Olympiad (IMO docu)

 

 
 
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$
(Note that gcd(x, y) denotes the greatest common divisor of integers x and y.)

 

Solution
Claim: We must have $ab+1 = 2$.
Proof: Assume the contrary. Then, we must have $ab+1 = m \geq 3$ (since $a, b\geq 1$). Note that $\gcd(a, m) = \gcd(a, ab+1) = \gcd(a, 1) = 1$ and $\gcd(b, m) = \gcd(b, ab+1) = \gcd(b, 1) = 1$.
Now, take some $n\equiv -1\pmod{\phi(m)}$ with $n \geq N$.
Then, we have that $$a^n + b \equiv \frac{1}{a} + b \equiv \frac{ab+1}{a} \equiv 0\pmod{m},$$
and likewise
$$b^n + a \equiv \frac{1}{b} + a \equiv \frac{ab+1}{b} \equiv 0\pmod{m}.$$
Therefore,
$$m\mid \gcd(a^n + b, b^n + a).$$
However, since $m\geq 3$, we cannot have $a\equiv b\equiv 1\pmod{m}$, since that would imply $2\equiv 0\pmod{m}$. Therefore, one of $a,b$ is not $1\pmod{m}$. WLOG suppose that $a$ was not $1\pmod{m}$. Then, $a^{n+1} \not \equiv a^n\pmod{m}$, so since $m\mid a^n + b$, we must have $m\nmid a^{n+1} + b$, so consequently $m\nmid \gcd(a^{n+1}+b, b^{n+1}+a).$ However, since $n\geq N$, we must have $\gcd(a^n+b, b^n+a) = \gcd(a^{n+1}+b, b^{n+1}+a)$, but the first expression is divisible by $m$, and the second expression is not, absurd. Thus, we have a contradiction and so we must have $ab+1 = 2$. $\square$

Thus, $ab = 1$, so $a=b=1$, which clearly works since the gcd is always $2$, so we're done.