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 3 of 5: The modulus divides one term exactly

Previous step Next step

In plain words

Multiplying $a^{n-1}+b$ by $a$ produces $a^n$ plus $ab$ , and Euler's theorem makes $a^n$ congruent to $1$ modulo $M$ , so this product is a multiple of $M$ ; the same works for the other side, forcing $M$ to divide their gcd.

M\mid x_{n-1}

Detailed analysis

Since $n\equiv0\pmod{\varphi(M)}$ and $\gcd(a,M)=1$ , Euler's theorem gives $a^n\equiv1\pmod M$ . Then $a(a^{n-1}+b)=a^n+ab\equiv1+(M-1)=M\equiv0\pmod M$ , and since $\gcd(a,M)=1$ this gives $M\mid a^{n-1}+b$ . Symmetrically $b^n\equiv1\pmod M$ gives $b(b^{n-1}+a)=b^n+ab\equiv0\pmod M$ , so $M\mid b^{n-1}+a$ . Hence $M\mid\gcd(a^{n-1}+b,b^{n-1}+a)=x_{n-1}$ .