If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$ 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.
 A: 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. 
A: Looking for a counterexample with $a$ is even and $b$  is odd and $\gcd(2^{a}+1,2^{b}+1)=k \gt 1$ then 


*

*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

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