Show $\,m$ odd $\Rightarrow \gcd(a^m-1,a^n+1)=1$ or $2$ Let $(2^m-1,2^n+1)=1$ and suppose $m$ is even.  Also, $m,n,k\in \mathbb{N}$.  We have
$$(2^{m}-1)x+(2^n+1)y=1$$
$$(2^{2k}-1)x+(2^n+1)y=1$$
$$(2^{2k}-1)y\equiv 1\pmod{2^n+1}$$
$$(2^k+1)(2^k-1)y\equiv 1\pmod{2^n+1}$$
I don't know now to proceed from here....
 A: ${d\mid\color{#0a0}{a^{\large m}\!-\!1}},\color{#90f}{a^{\large n}\!+\!1}\,$
$\Rightarrow\,
 {\rm mod}\ d\!:\,\color{#0a0}{a^{\large m}\! \equiv}\!\!\!\!\!\!\!\!\overset{\Large\ [\,\color{#90f}{ -1\ \equiv\ a^{\LARGE n}}]^{\LARGE\color{#c00}2}\ \ \ \ }{ 1\color{#c00}{\equiv {\color{#90f}{a^{\large \color{#c00}2n}}}}}\!\!\!\!\!\!\!\!$
$\Rightarrow
 {\rm ord}\,a\:\!|\:\!\overbrace{(\color{#0a0}m,\color{#90f}{\color{#c00}2n})\!=\! (m,n)}^{\Large{\rm\ \ by}\ \color{#0a0}m\ \rm odd}\:\!|\:\!\color{#c00}n\,$
$\Rightarrow 
 \overbrace{\color{#c00}{\bf 1}\equiv\color{#90f}{a^{\large\color{#c00} n}\!\equiv -1}}^{\color{#08f}{\!\!\!\!\!\!\Large\Rightarrow\,\ d\ \mid\  2^{\phantom{|^|}}}}$
So either they are coprime, or they have $\color{#08f}{{\rm gcd}\,\ d = 2}\ (\!\iff\! a\,$ is odd).
Remark $ $ It's $\:\!\color{#0a0}m$ odd, $\:\!\color{#c00}{k\!=\!2}\,$ case of $\,\rm\color{#00f}E$ = Euclid's Lemma in the exponents below
Lemma $\,\ $ If $\ (\color{#0a0}m,\color{#c00}k)=1\,$ then $\, a^{\large\color{#0a0}m}\equiv 1\equiv a^{\large\color{#c00}{k}\:\!n}\, $ $\Rightarrow\, a^{\large n}\equiv 1$
Proof $\ \ {\rm ord}\ a\mid m,kn\, \Rightarrow\, {\rm ord}\ a\mid \underbrace{(\color{#0a0}m,\color{#c00}kn)\!\overset{\rm\color{#00f}E}=\!(m,n)}_{\large (\color{#0a0}m,\,\color{#c00}k)\,=\,1\qquad\!}\mid n\,\Rightarrow\, a^{\large n}\equiv 1$
The same idea occurs frequently in various guises, e.g. below is a fractional form.
Lemma $ $ If a fraction is writable with denominator $\,m\,$ and also with denominator $\,kn\,$ where $(\color{#0a0}m,\color{#c00}k)=1$ then the fraction can  be written with denominator $\,n$.
Proof $ $ Recall that the least denominator $\,d\,$ divides every other denominator hence, just as above,
$d\mid m,kn\,\Rightarrow\, d\mid (\color{#0a0}m,\color{#c00}kn) \overset{\rm\color{#00f}E}= (m,n)\mid n\ $ so $\,d\mid n,\,$ therefore scaling the fraction with least denominator $\,d\,$ by $\,n/d\,$ yields an equivalent fraction with denominator $\,n$.

Alternatively we could employ  $\,(a^m-1,a^j-1) = a^{(m,j)}-1\ $ (for $\,j=kn),\,$ whose proof is exactly the same as in the above Lemma, using divisibility by $\:\!{\rm ord}\, a$.
We can abstract out these similarities and present unified proofs after we have studied the
pertinent algebraic structures: $ $ ideals and modules (viz. order ideals and  denominator ideals)
