If $\gcd(a,b)=1$ , and $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$? How to prove that:

$\gcd(a,b)=1 \Rightarrow \gcd(2^{a}+1,2^{b}+1)=1$ ,where $a$ is even and $b$ is odd natural number

For example:
$\gcd(2^8+1,2^{13}+1)=1 , \gcd(2^{64}+1,2^{73}+1)=1$
I know that Knuth showed that:
$\gcd(2^{a}-1,2^{b}-1)=2^{\gcd(a,b)}-1$
so: $\gcd(a,b)=1\Rightarrow \gcd(2^{a}-1,2^{b}-1)=1$
but I don't see whether this fact is useful. 

This is a minor tweak of my answer to an earlier post by user952949.  That one asked for a proof that if $a$ and $b$ are relatively prime and odd, then $\gcd(2^a+1,2^b+1)=3$.
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}.$$
If $(-1)^u=(-1)^v$, we find that $1\equiv 0\pmod{m}$, so the only positive common divisor of $2^a+1$ and $2^b+1$ is $1$.  If $(-1)^u=-(-1)^v$, we find that $3\equiv 0\pmod{m}$.
If we only know that $3\equiv 0\pmod{m}$, then all we can say is that any common divisor of $2^a+1$ and $2^b+1$ divides $3$.  
We need to rule out the possibility that $3$ divides both of $2^a+1$ and $2^b+1$. This is easy. One of $a$ or $b$ is even, say $a$. Then $2^a\equiv 1 \pmod{3}$, so $2^a+1$ is not divisible by $3$. 
