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.  

Hint:
Consider the following proof when $a=2$: https://planetmath.org/fermatnumbersarecoprime
Try adapting it to work for all $a$.
Hint 2: Factor $a^{2^n}-1$.
