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)?

If $d\mid 2^a+1$, then $2^a \equiv -1 \pmod d$.  But then that means that the order of $2\pmod d$ must be a divisor of $2a$.  Similarly, if $d\mid 2^b +1$, the order of $2 \pmod d$ must divide $2b$.  But that means that order of $2\pmod d$ must divide $(2a,2b)=2$.  So the order of $2\pmod d$ must be a divisor of $2$, or $2^2=1\pmod d$.  So $d=3$ or $d=1$.
