Given that $p$ is an odd prime, is the GCD of any two numbers of the form $2^p + 1$ always equal to $3$?

Question

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.

Answer 1

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.

Answer 2

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$.