Problem 2

For which pairs of positive integers

(a,b)

is the sequence

\gcd(a^n+b,b^n+a)

n=1,2,\ldots

, eventually constant?

Step 5 of 5: Finish using

x_{n+1}

Previous step Next step

In plain words

Repeating the same argument one step later shows $a^{n+1}+b$ is congruent to $a+b$ modulo $M$ , and since $a$ and $b$ are both $-1$ modulo $M$ , this quantity is $-2$ , which forces $M$ to be at most $2$ , leaving only the trivial pair.

M\mid2\implies a=b=1

Detailed analysis

Since $x_{n+1}=x_n$ , also $M\mid a^{n+1}+b$ . Now $a^{n+1}=a^n\cdot a\equiv1\cdot a\equiv a\equiv-1\pmod M$ (Step 4), so $a^{n+1}+b\equiv-1+b\equiv-1-1=-2\pmod M$ , forcing $M\mid2$ . Since $M=ab+1\ge2$ for positive integers $a,b$ , this gives $M=2$ , i.e. $ab=1$ , so $a=b=1$ . Together with Step 1, the only pair for which the sequence is eventually constant is $(a,b)=(1,1)$ .