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 2 of 5: Set up the key modulus

Previous step Next step

In plain words

The number $ab+1$ is designed so that $a$ and $1/a$ are close to $-b$ and $-1/b$ respectively modulo $M$ , which will let Euler's theorem interact nicely with the sequence once $n$ is a suitable multiple of the totient of $M$ .

M=ab+1,\quad \gcd(a,M)=\gcd(b,M)=1

Detailed analysis

Suppose $x_n:=\gcd(a^n+b,b^n+a)$ is eventually constant, and set $M=ab+1$ . Since $a\mid M-1$ , $\gcd(a,M)=1$ , and likewise $\gcd(b,M)=1$ . Choose $n$ to be a sufficiently large multiple of $\varphi(M)$ so that $x_{n-1}=x_n=x_{n+1}$ .