Given that $p$ is an odd prime, is the GCD of any two numbers of the form $2^p + 1$ always equal to $3$? I have checked it for some numbers and it appears to be true. Also I am able to reduce it and get the value $3$ for specific primes $p_1$, $p_2$ by using the Euclidean algorithm but I am not able to find a general argument for all numbers.
 A: Let $p_1, p_2$ be any two distinct prime numbers and assume that 
$$q \mid2^{p_1} + 1 \, \mbox{ and } \, q \mid 2^{p_2} + 1$$
Then 
$$2^{p_1} \equiv -1 \equiv 2^{p_2} \pmod{q}$$ 
In particular, there exists a power of $2$ which is $-1 \pmod{q}$. Let $a$ be the smallest number for which $2^a \equiv -1 \pmod{q}$ and let $b$ be the order of $2 \pmod{q}$. Then $b \mid 2a$, thus $2a = bk$ for some integer $k$.
Now, since $2^{p_1} = 2^a$ we have 
$$b \mid p_1 - a$$ and hence 
$$b \mid 2p_1 - 2a = 2p_1 - bk$$
This shows that $b \mid 2p_1$. Exactly same way we get that $b \mid 2p_2$. As $p_1, p_2$ are distinct primes we get $b \mid 2$.
This shows that 
$$2^2 \equiv 1 \pmod{q}$$
and hence $q = 3$.
This shows that $\gcd(2^{p_1} + 1, 2^{p_2} + 1) = 3^\mathcal{L}$ for some $\mathcal{L}$. 
Finally, if $9 \mid 2^p + 1$ then 
$$2^p \equiv -1 \pmod{9} \Rightarrow 2^p \equiv 2^3 \pmod{9} \Rightarrow 6 \mid p - 3 $$
This shows that $9 \mid 2^p + 1$ only in the case $p = 3$.
Therefore, for all distinct primes $p_1, p_2$ we must have
$$\gcd(2^{p_1} + 1, 2^{p_2} + 1) \mid 3$$
The claim can be easily completed by observing that $2^p + 1$ is divisible by $3$ for odd primes $p$.
P.S.  An alternate way to continue after $2a = bk$ is as follows:
$2 \mid bk$ implies $2 \mid b$ or $2 \mid k$. But $2 \mid k$ is impossible, as it would imply that $b \mid a$ and hence $2^a \equiv 1 \pmod{q}$.
Therefore $b$ is even, and as 
$$(2^{\frac{b}{2}})^2=1 \pmod{q}$$
we get
$$2^{\frac{b}{2}}= \pm 1 \pmod{q}$$
Since $b$ is the order, the above cannot be $1$ and thus it is $-1$. Therefore, the minimality of $a$ implies that
$$a \leq \frac{b}{2} \Rightarrow 2a \leq b$$
As $b \mid 2a$ we get $b = 2a$. 
Now, 
$$a \mid b \mid p_{1, 2} - a$$
implies that $a \mid p_{1,2}$ therefore $a = 1$. This shows that
$$2^{1} \equiv -1 \pmod{q}$$
and hence $q = 3$. 
A: In general, the following statement is true. Let $a,b$ be positive integers and $m\ge 2$ an integer. Then
$$
\gcd(m^a-1,m^b-1)=m^{\gcd(a,b)}-1.
$$
This can be proved by considering the Euclidean algorithm in base $m$,
see the references here.
Edit: As pointed out by Daniel, one can show in a similar way that
$$
\gcd(m^a+1,m^b+1)\mid m^{2\gcd(a,b)}-1.
$$
For $m=2$ and $p,q$ different odd primes we have equality.
