Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$ 
Let $a$ and $b$ be two odd positive integers. Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$.

I tried rewriting it to get $\gcd(2^{2k+1}+1,2^{\gcd(2k+1,2n+1)}-1)$, but I didn't see how this helps.
 A: Consider $r=\gcd(a,b)$ and write $a=rs$. Then you are reduced to finding
$$
\gcd(2^{rs}+1,2^r-1)=\gcd(2^{rs}+2^r,2^r-1)
$$
Since $2^r-1$ is odd and $2^{rs}+2^r=2^r(2^{rs-r}+1)$, we have
$$
\gcd(2^{rs}+2^r,2^r-1)=\gcd(2^{r(s-1)}+1,2^r-1)
$$
If $s=1$, we are done. Otherwise we apply the same argument to conclude
$$
\gcd(2^{r(s-1)}+1,2^r-1)=\gcd(2^{r(s-2)}+1,2^r-1)
$$
and go on.
Turn it into a proper proof by induction.
A: If $p$ is a prime dividing $2^{\gcd(a,b)}-1,$ then $2^{\gcd(a,b)}\equiv1\pmod p.$ Since $\gcd(a,b)\mid a,$ we also have $2^a+1\equiv(2^{gcd(a,b)})^{a/\gcd(a,b)}+1\equiv1+1=2\pmod p.$ Since $2^{\gcd(a,b)}+1$ is odd, $p$ is odd too, thus $p$ does not divide $2^a+1.$ This shows that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1.$  
Hope this helps.
A: We $\gcd(a, b)$ is a divisor of $a$, so we have $a=m\gcd(a, b)$. Therefore, we can rephrase the question as:
$$\gcd\left(2^{m\gcd(a, b)}+1, 2^{\gcd(a, b)}-1\right)$$
Now, since $1$ is a zero for $x^m-1$, so we know that:
$$(x-1) \mid (x^m-1)$$
Substitute $x=2^{\gcd(a, b)}$:
$$(2^{\gcd(a, b)}-1) \mid (2^{m\gcd(a, b)}-1)$$
Subtract the latter part of this statement from the former part of the $\gcd$:
$$\gcd(2, 2^{\gcd(a, b)})$$
The latter part is clearly odd, so the $\gcd$ is $1$.
A: Any divisor of $2^{\gcd(a,b)}-1$ is a divisor of $2^a-1$  since $a$ is a multiple of $\gcd(a,b)$ by definition. 
Hence $\;\gcd(2^a+1, 2^{\gcd(a,b)}-1)=\gcd(2^a+1, 2^a-1) =1$.
A: Let $\ \ d\, =\, (\color{#0a0}{2^A+\ 1},\,\ \ \color{#c00}{2^C\:-\:1}).\, $ $\ A\, =\, C\,N\,\ $ by $\,\ C = (A,B)\mid A,\ $   so
${\rm mod}\ d\!:\: \color{#0a0}{{-}1\equiv}{\color{#0a0}{ 2^A}\!\equiv (\color{#c00}{2^C})^N}\!\equiv\! \color{#c00}{1}^N\!\equiv 1\:\Rightarrow\:d\mid 2\:\Rightarrow\: d=1\:$ by $\,d\,$ odd.
