Show $\,m$ odd $\Rightarrow \gcd(a^m-1,a^n+1)=1$ or $2$

Question

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....

Answer 1

${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)