$(a^{2^n}+1,a^{2^m}+1)=1 or 2$ [duplicate]

Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.

I solve the problem in the following way: I assume that $m>n$ then $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.

But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.

Any idea?

Thanks!

Solution 1:

If we have $n < m$, then

$$(a^{2^n} + 1)\cdot (a^{2^n} - 1) = a^{2^{n+1}} - 1$$

shows $(a^{2^n}+1) \mid (a^{2^{n+1}}-1)$. Then

$$(a^{2^k}-1)\cdot(a^{2^k}+1) = a^{2^{k+1}}-1$$

shows $(a^{2^{n+1}}-1) \mid (a^{2^m}-1)$, and thus

$$\gcd(a^{2^m}+1, a^{2^n}+1) = \gcd((a^{2^m}-1)+2,a^{2^n}+1) = \gcd(2, a^{2^n}+1).$$