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

One of the possible form of odd coprime numbers is:
$a=2m-n$ and $b=m$ , (see this page)
So we may write following equalities:
$2^{a}+1=2^{2m-n}-2+3=2(2^{2m-n-1}-1)+3$
$2^{b}+1=2^{m}-2+3=2(2^{m-1}-1)+3$
So in order to prove that $\gcd(2^{a}+1,2^{b}+1)=3$ we need to prove that:
$\gcd(2^{2m-n-1}-1,2^{m-1}-1)=2^{\gcd(2m-n-1,m-1)}-1=3\cdot p $ for some natural number $p$
The last equality is true only if: $\gcd(2m-n-1,m-1)=2\cdot k$ (even number) for all $m,n$.
Since $m$ and $n$ are odd numbers you can easily show that this is always true.
Similarly you can show for other two forms of $a$ and $b$ that $\gcd(2^{a}+1,2^{b}+1)=3$
