<s>[INST] How to find $\gcd(a^{2^m}+1,a^{2^n}+1)$ when $m \neq n$? How to prove the following equality?
For $m\neq n$,
$\gcd(a^{2^m}+1,a^{2^n}+1) = 1 $ if $a$ is an even number
$\gcd(a^{2^m}+1,a^{2^n}+1) = 2 $ if $a$ is an odd number
Thanks in advance.
 [/INST] Let $p$ divides $a^{2^n}+1\implies a^{2^n}\equiv-1\pmod p$
If $m>n,$ taking  $2^{m-n}$th power, $(a^{2^n})^{2^{m-n}}\equiv(-1)^{2^{m-n}}\pmod p\implies a^{2^m}\equiv1\pmod p$
So, $p$ divides $ a^{2^m}-1$
If $p$ divides $ a^{2^m}+1,p$ will divide $(a^{2^m}+1)-(a^{2^m}-1)=2$ 
So, if $a$ is even, $a^{2^n}+1$ will be odd $\implies p=1\implies $ gcd$(a^{2^m}+1,a^{2^n}+1)=1$
Similarly, for odd $a$ 

Alternatively, WLOG let $m>n,a^{2^n}=b$(say) and $m=n+r$ where integer $r>0$
$\implies a^{2^m}+1=a^{2^{n+r}}+1=(a^{2^n})^{2^r}+1=b^{2^r}+1$
Now, $b^2-1=(b+1)(b-1)$
$(b^2)^2-1=(b^2+1)(b^2-1)=(b^2-1)(b+1)(b-1)$
$\cdots$
$b^{2^r}-1=(b^{2^{r-1}}+1)(b^{2^{r-1}}-1)\cdots(b^4+1)(b^2+1)(b+1)$
Now, $gcd(b^{2^r}+1,b^{2^r}-1)=gcd(b^{2^r}+1-(b^{2^r}-1),b^{2^r}-1)$
$=gcd(2,b^{2^r}-1)= \begin{cases} 2 &\mbox{if } b \mbox{ is odd} \\
1 & \mbox{if } b \mbox{ is even }\end{cases} $
As $(b+1)$ divides $(b^{2^r}-1),gcd(b^{2^r}+1, b+1)$ will divide $gcd(b^{2^r}+1,b^{2^r}-1)$
Observe that  if $b$ is odd, $gcd(b^{2^r}+1,b^{2^r}-1)=2$ and 
$b^{2^r}+1, b+1$ are both even , hence $ gcd(b^{2^r}+1, b+1)=2\implies gcd(a^{2^m}+1,a^{2^n}+1)=2$ 
Similarly, for even $b$ 
</s>