Compute $(a^{2^m}+1,a^{2^n}+1)$ I need your uncaring objective eyes. The hint for the problem was: show that for a given $m>n$ $A_n|A_m-2$. So here my attempt: $A_m-2=a^{2^m}-1$, additionally I can write $m=n+k$ and therefore I can calculate $\frac{a^{2^{n+k}}-1}{a^{2^{n}}+1}=\frac{\left(a^{2^{n}}\right)^{2^k}-1}{a^{2^{n}}+1}=\frac{b^{2^k}-1}{b+1}$, setting $b=a^{2^n}$. Now by a division one may find that $(b^{2^k}-1)=(b+1)\cdot(b^{2^k-1}-b^{2^k-2}+\ldots +b-1)$ which proves the point. Now we can use the statement: $A_n|A_m-2\Rightarrow \exists k:k\cdot A_n = A_m -2\Rightarrow 2=A_m-k\cdot A_n$. Since $d$ has to divide the right side, it has to divide the left side. So: $d=2$. Is this reasonable?

From the calculation, we can only conclude that our gcd _divides_ $2$, and therefore the gcd cannot be anything other than $1$ or $2$.

Each is possible. If $a$ is odd then the gcd is $2$, and if $a$ is even then the gcd is $1$.