If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

Question

How to prove that:

If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

This statement is generalization of the statement from my previous question.

I have checked for many $(a,b)$ pairs using Maple, and $\gcd(2^{a}+1,2^{b}+1)$ is always $1$

For example : $\gcd(2^{66}+1,2^{33}+1)=1 , \gcd(2^{4422}+1,2^{3333}+1)=1$ and so on.

Answer 1

Looking for a counterexample with $a$ is even and $b$ is odd and $\gcd(2^{a}+1,2^{b}+1)=k \gt 1$ then

1. the order of $2 \mod k$ is must be odd for $a$ and $b$ to have different parities, and so the order of $2 \mod p$ of any prime factor $p$ of $k$ must also be odd
2. $k$ divides both $2^{a}+1$ and $2^{b}+1$ and so any prime factor $p$ of $k$ divides both $2^{a}+1$ and $2^{b}+1$

This is not possible, since the primes $p$ such that the order of $2 \mod p$ is odd (OEIS A014663) are also the primes $p$ which do not divide $2^n+1$ for any $n$. Since there are no counterexamples with $a$ and $b$ different parities, the assertion is true.

Answer 2

The following result is well-known. Solutions have even been posted on this site: $$\gcd(2^{x}-1,2^{y}-1)=2^{\gcd(x,y)}-1.$$ Let $d=\gcd(a,b)$. Then $\gcd(2a, 2b)=2d$, and therefore $$\gcd((2^{2a}-1,2^{2b}-1)=\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))=2^{2d}-1.$$ Since $d$ is odd, $2d$ divides $a$, and therefore $2^{2d}-1$ divides $2^a-1$. Note also that $\gcd(2^a+1,2^a-1)=1$ (unless $a=0$). Now we have all the pieces we need.

We are trying to prove that $\gcd(2^a+1,2^b+1)= 1$. Suppose to the contrary that the gcd is $>1$. Then there is a prime $p$ that divides both $2^a+1$ and $2^b+1$. Thus $p$ divides $\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))$, so $p$ divides $2^{2d}-1$. But $2^{2d}-1$ is a factor of $2^a-1$, so $p$ divides $2^a-1$.

Since $2^a+1$ and $2^a-1$ are relatively prime, $p$ cannot divide $2^a+1$, and we have our contradiction.