Let $m,n,k\in\mathbb{N}$ such that $n= 2k-1$ ($n$ is odd). Find $(2^m +1, 2^n -1)$, where by $(a,b)$ we mean the greatest common divisor of $a,b$.
Attempt:
Let $(2^m +1, 2^n -1)=:d$, then $$d\mid (2^m+1)\land d\mid (2^n -1)\Rightarrow d\mid (2^m + 2^n)\Leftrightarrow d\mid (2^m+2^{2k-1})$$
If $m\geq 2k-1$, that is $m=2k-1+r, r\in\mathbb{N}\cup\{0\}$, then $d\mid 2^{2k-1}(2^r+1)$ and I'm stuck. What should I do from here? How would $n$ being odd help the case?
Was told to use the euclidean algorithm here, but I don't understand what was meant by that.
References to similar problems would be appreciated.
Assuming that you know the general formula: 1$$\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1 \tag 1$$ You can apply $(1)$ for $(a,b)=(2m,n)$ and $(a,b)=(m,n)$ you will obtain:
$$\begin{align}\gcd(2^{2m}-1,2^n-1)&=2^{\gcd(2m,n)}-1=2^{\gcd(m,n)}-1=d \tag 2 \\ \gcd(2^{m}-1,2^n-1&)=2^{\gcd(m,n)}-1=d `\tag3\end{align}$$
And from here you can see if $x=2^m-1,y=2^m+1$ and $z=2^n-1$ you have: $$\gcd(xy,z)=\gcd(x,z)=d $$
You can conclude that $\gcd(y,z)=1 $