<s>[INST] 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)?
 [/INST] A very useful fact: If $a$ and $b$ are relatively prime, there exist integers $x$ and $y$ such that $ax+by=1$.  
We can arrange for $x$ to be $\ge 0$ and $y$ to be $\le 0$. So there are non-negative integers $u$ and $v$ such that $au=bv+1$. Thus 
 $$2^{au}=2^{bv+1}=2\cdot 2^{bv}.  \qquad\text{(Equation 1)}$$
Let $m$ be any common divisor of $2^a+1$ and $2^b+1$. Then $2^a \equiv -1\pmod{m}$ and $2^b\equiv -1 \pmod m$. It follows that 
$$2^{au} =(2^a)^u \equiv (-1)^u \pmod{m} \qquad\text{and}\qquad 2^{bv} =(2^b)^v \equiv (-1)^v \pmod{m}.$$
From Equation $1$, we conclude that
$$(-1)^u \equiv 2\cdot (-1)^v\pmod{m}.$$
 Since $a$ and $b$ are odd, $u$ and $v$ have opposite parity.  Thus $-1\equiv 2\pmod {m}$, that is, $3\equiv 0 \pmod m$, and therefore $m$ divides $3$.
If $c$ is odd, then $2^c\equiv -1\pmod{3}$, so $3$ divides $2^c+1$.  Thus $3$ divides our gcd. But our gcd  divides $3$, so it is $3$.
</s>