Prove that if $a,m,n \in \mathbb{Z}^+$ and $m \ne n$ then $\gcd(a^{2^m}+1,a^{2^n}+1)$ is 1 if a is even and 2 if a is odd.

Question

I know that if a pime q|a^2^m+1 and q divides a^2^n+1 then q divides their sum and difference but i don't know how to proceed further. please help

Answer 1

Applying this answer: wlog $\,m < n\,$ so $\,d = (2^m,2^n) = 2^m,\ b = 1,\ c = 2^{n-m}.\ $ Thus $\,2\nmid b-c\,$ so the formula there implies that the gcd $ = (a^d+1,2) = 1$ if $a$ is even, and $2$ if $a$ is odd.

---

Alternatively a more direct proof follows as below (from this answer on Fermat numbers).

${\bf Hint}\rm\quad\ \ \gcd(c+1,\,\ c^{\large 2k}\!+1)\ =\ gcd(c+1,\:2)$

${\bf Proof}\rm\ \ \ mod\ c+1\!:\,\ c^{\large 2k}\!+1\: \equiv\ (-1)^{\large 2k}\!+1\:\equiv\ 2,\ \ {\rm by}\ \ c\equiv -1\quad {\bf QED}$

Specializing $\rm\,\ c=a^{\large 2^{\Large M}},\ \ 2k = 2^{\large \,N-M}\ \Rightarrow\ c^{\large\, 2k} = a^{\large 2^{\Large N}}\ $ immediately yields your claim.

Remark $\ $ Aternatively, one could employ that $\rm\:c^{\large 2k}\!+1\, =\, (c^{\large 2k}-1) + 2\:\equiv\: 2\pmod{c+1}\ $
by $\rm\ c+1\ |\ c^{\large 2}-1\ |\ c^{\large 2k}\!-1.\, $ But this requires some ingenuity, whereas the above proof does not, being just a trivial congruence calculation using the modular reduction property of the $\rm\:gcd,\:$ namely $\rm\ \gcd(a,b)\, =\, \gcd(a,\:b\ mod\ a),\:$ a reduction which applies much more generally. $ $ Said equivalently, the result follows immediately by applying a single step of the Euclidean algorithm. Notice how abstracting the problem a little served to greatly elucidate the innate structure.