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 4 of 5: Use

x_n

to pin down a and b modulo M

Previous step Next step

In plain words

Since $x_n$ equals $x_{n-1}$ , the modulus $M$ also divides $x_n$ , meaning it divides $a^n+b$ and $b^n+a$ directly; combined with $a^n$ and $b^n$ both being $1$ modulo $M$ , this forces $b$ and $a$ to each be $-1$ modulo $M$ .

a\equiv b\equiv-1\pmod M

Detailed analysis

Since $x_n=x_{n-1}$ and $M\mid x_{n-1}$ (Step 3), also $M\mid x_n$ , so $M\mid a^n+b$ and $M\mid b^n+a$ . Using $a^n\equiv1,b^n\equiv1\pmod M$ , this gives $0\equiv1+b\pmod M$ and $0\equiv1+a\pmod M$ , i.e. $a\equiv b\equiv-1\pmod M$ .