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.
 A: 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$ 
A: Wlog. $m>n$.
Let $p$ be a divisor of $\gcd(a^{2^m}+1,a^{2^n}+1)$,. Then especially $p|a^{2^m}+1$, i.e. $a^{2^n}\equiv -1\pmod p$ and $$a^{2^m}=(a^{2^n})^{2^{m-n}}\equiv (-1)^{2^{m-n}}\equiv 1^{2^{m-n-1}}\equiv 1\pmod p.$$
As also $p|a^{2^m}+1$, we conclude $p|2$, i.e. 
$$ \gcd(a^{2^m}+1,a^{2^n}+1)=2^k\qquad\text{for some }k\ge0.$$
If $a$ is even, $a^{2^n}+1$ and $a^{2^m}+1$ are odd, thus implying $k=0$.
If $a$ is odd, then $a^{2^n}+1$ and $a^{2^m}+1$ are even, hence $k\ge1$.
On the othre hand, odd squares are always $\equiv 1\pmod 8$, hence we take gcd of numbers $\equiv 2\pmod 8$, i.e. they are not multiples of $4$, hence $k=1$.
A: Hint  $\rm\,\ d\mid 1\!+\!a^{\large 2^N}\!\!\!,\,1\!+\!a^{\large 2^{N+K}}\!\!\Rightarrow\:   mod\ d\!:\ a^{\large 2^N}\!\equiv \color{#c00}{-1}\equiv a^{\large 2^{N+K}}\!\! \equiv(a^{\large2^N}\!)^{\large {2^K}}\!\!\!\equiv(\color{#c00}{-1})^{\large {2^K}}\!\!\equiv\color{#c00}1\:\Rightarrow\:d\mid\color{#c00}{1\!+\!1}$
