Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$ 
Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$.

I was thinking among the lines of:
Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist integers $x$ and $y$ such that, $ax+by=1$. 
Then, $a=(1-by)/x$, $b=(1-ax)/y$
So if I write $2^a+1$ as:
$2^{(1-by)/x}+1$
Then can I say that the above expression is equivalent to 0 (mod 3)?

Note that both $2^a+1$ and $2^b+1$ are odd, so any common divisor is odd.
Now, if $d$ divides $2^a+1$ and $2^b+1$, then it also divides $(2^a+1)-(2^b+1) = 2^a-2^b$, hence it divides $2^{\min(a,b)}(2^{|a-b|}- 1)$. But since $d$ is odd, then $d$ divides $2^{|a-b|}-1$. That is, if, say, $a\geq b$, then
$$d|2^{a}-1,2^b-1 \Longleftrightarrow d|2^a-1, 2^b-1, 2^{a-b}-1.$$
But if $d$ divides both $2^{a-b}-1$ and $2^b-1$, then it divides 
$$2^b(2^{a-b}-1) + (2^b-1) = 2^a-1.$$
So:
$$d|2^a-1,2^b-1 \Longleftrightarrow d|2^b-1, 2^{a-b}-1.$$
We are assuming $a\geq b$; be careful with that assumption; more generally, we have:
$$\text{For }a,b\text{ odd, }\gcd(2^a-1,2^b-1) = \gcd(2^{\min(a,b)}-1, 2^{|a-b|}-1).$$
This looks very much like the gcd identity
$$\gcd(x,y) = \gcd(y,x-y),$$
which is very useful. Maybe you can make it work for you?
