Prove that two distinct numbers of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if $a$ is even and have $\gcd=2$ if $a$ is odd 
Prove that two distinct numbers of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if $a$ is even and have $\gcd=2$ if $a$ is odd.

My attempt:
If $a$ is even, let $a = 2^{s}k$ for some integers $k, s$
Then, $$a^{2^{n}} + 1 = 2^{2^{n}s}\cdot k^{2^n} + 1$$ and $$a^{2^{m}}  + 1 = 2^{2^{m}s}\cdot k^{2^m} + 1$$
To prove that they're relatively prime, we need to show that their gcd = 1.
And I was stuck here, how could I prove that gcd of two numbers is $1$?   
A hint would be sufficient. Thanks.  

Proof $\   (A\!+\!1, A^{2K}\!\!+1)\,=\, (A\!+\!1,\ (-1)^{2K}\!+1) = (A\!+\!1,2),\, $ [OP is $ A = a^{\large 2^{\Large N}}\!\!,\,$ wlog $N\! <\! M$]  
using $\,\ \  (A\!-\!n,\ \ F(A)\ )\,   = \,  (A\!-\!n,\ \ F(n) )\  $ for all polynomials $\ F(X)\in \mathbb Z[X],\  A,n\in \mathbb Z$ 
by $\!\bmod A\!-\!n\!:\ A\equiv n\,\Rightarrow\, F(A)\equiv F(n)\ $ by the Polynomial Congruence Rule, and
also by $\ (B,\ C)\ =\ (B,\ C \bmod B) = $ modular property of GCD (used in Euclidean algorithm)
Remark $\, $ For the general case $\ (a^m+1,a^n+1)\ $ see this answer.
