Find the greatest common divisor of $2^m+1$ and $2^n+1$ that $m,n$ are positive integers.

This started as a partial solution, trying to bundle up what's been said in the comments and a bit more. After some more comments (esp. from Empy2) it is now a complete solution.

Proposition 1 gives an upper bound for the gcd. Proposition 2 then shows that this upper bound is actually assumed under certain conditions on $m,n$. Proposition 3 then shows that if those conditions are not fullfilled, the gcd is $1$.

Proposition 1:

$$\gcd(2^{m}+1,2^{n}+1) | 2^{\gcd(m,n)}+1.$$

Proof:

Let $d$ be a common divisior of $2^m+1$ and $2^n+1$.

We have $2^m+1|2^{2m}-1$ and $2^n+1|2^{2n}-1$, so it follows that $d|\gcd(2^{2m}-1,2^{2n}-1)$ and we know that $$\gcd(2^{2m}-1,2^{2n}-1) = 2^{\gcd(2m,2n)}-1 = 2^{2\gcd(m,n)}-1 = (2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1),$$

so

$$d|(2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1). \tag{1} \label{eq1}$$

Let $p$ be a prime divisor of $2^{\gcd(m,n)}-1$. That means

$$2^{\gcd(m,n)} \equiv 1 \pmod p$$

and if we raise each side to the $\frac{m}{\gcd(m,n)}$-th power, we obtain

$$2^m \equiv 1 \pmod p \Longrightarrow 2^m+1 \equiv 2 \pmod p$$

Because $m > 0$, $2^m+1$ is odd, so $p \neq 2$ and hence $2^m+1 \neq 0 \pmod p$.

That means no prime divisor of $2^{\gcd(m,n)}-1$ can be a divisor of $2^m+1$, so $d$ and $2^{\gcd(m,n)}-1$ are coprime and we get from \eqref{eq1} that

$$d|2^{\gcd(m,n)}+1$$

and Proposition 1 follows.

---

Proposition 2: When $m$ and $n$ contain the exact same power of $2$:

$$m=2^km', n=2^kn';\quad m'\equiv n'\equiv1 \pmod 2,$$

then

$$\gcd(2^{m}+1,2^{n}+1) = 2^{\gcd(m,n)}+1.$$

Proof:

In this case we also set $m'=\gcd(m',n')m''$ and $n'=\gcd(m',n')n''$ and find

$$2^m+1=2^{2^km''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{m''}+1$$

and the equivalent for $n$:

$$2^n+1=2^{2^kn''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{n''}+1.$$

Since $m''$ and $n''$ are odd, that means that $2^{2^k\gcd(m',n')} +1$ divides both terms (as per $(a+b)|(a^r+b^r)$ for any odd $r$).

Since $2^k\gcd(m',n') = \gcd(m,n)$, this proves Proposition 2.

---

The hard case seems to be when $m$ and $n$ contain different powers of $2$. I see no good way to attack that question in a general way, but maybe others do.

ADDED: It turns out that the comment by Empy2 below actually solves that problem, it just took me a while to realize that.

Proposition 3:

Let $m=\gcd(m,n)m'$ and $n=\gcd(m,n)n'$. If $m'$ is even and $n'$ is odd, then

$$\gcd(2^m+1,2^n+1)=1.$$

Proof: The conditions on $m'$ and $n'$ are equivalent to $m$ and $n$ containing different powers of $2$, where I assumed w.l.o.g. that $m$ was the one containing the higher power of $2$.

We have ${\rm{lcm}}(m,n)=\gcd(m,n)m'n'$ so

$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)m'}\right)^{n'}+1 = \left(2^{m}\right)^{n'}+1.$$

Since $n'$ is odd, we find that

$$2^m+1|\left(2^{m}\right)^{n'}+1 = 2^{{\rm lcm}(m,n)}+1.$$

Doing the same for $n$ we get

$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)n'}\right)^{m'}+1 = \left(2^{n}\right)^{m'}+1.$$

We finally have $$2^n+1|(2^n)^2-1|(2^n)^{m'}-1=2^{{\rm lcm}(m,n)}-1,$$ where the second divisibility follows because $m'$ is a multiple of $2$ (it was even).

So, as Empy 2 said, we have

$$2^m+1| 2^{{\rm lcm}(m,n)}+1,$$ $$2^n+1| 2^{{\rm lcm}(m,n)}-1,$$

so any common divisor of $2^m+1$ and $2^n+1$ must be a divisor of $2$. Since $m,n$ were both assumed to be positive, only $1$ can be a such common divisor.

---

Your conjectured formula is correct; here is the proof.

For integer $m,n\ge 0$, let $d(m,n):=\gcd(2^m+1,2^n+1)$. Assuming for definiteness $m\ge n$, we have \begin{align*} d(m,n) &= \gcd(2^m-2^n,2^n+1) \\ &= \gcd(2^n(2^{m-n}-1),2^n+1) \\ &= \gcd(2^{m-n}-1,2^n+1) \\ &= \gcd(2^{m-n}+2^n,2^n+1). \end{align*} If $m\ge 2n$, then this can be taken a little further, by factoring out $2^n$, to get $$ d(m,n) = \gcd(2^{m-2n}+1,2^n+1); $$ if $m\le 2n$, then factoring out $2^{m-n}$ instead of $2^n$ we get $$ d(m,n) = \gcd(2^{2n-m}+1,2^n+1). $$ In any case, we have the recursive relation $$ d(m,n) = d(|m-2n|,n),\quad m\ge n. \tag{$\ast$} $$

Let $\nu(k)$ denote the $2$-adic valuation of an integer $k\ne 0$; that is, $\nu(k)$ is the largest integer such that $2^{\nu(k)}$ divides $k$. I claim that

(1) If $m>n>0$, then $\max\{|m-2n|,n\}<\max\{m,n\}$;

(2) if $m>0$ or $n>0$, then $\gcd(|m-2n|,n)=\gcd(m,n)$;

(3) if $m\ne 2n$, then $\nu(m)=\nu(n)$ if and only if $\nu(m-2n)=\nu(n)$.

The first two assertions are easy to verify. For the last one, let $k:=\nu(n)$ and $l:=\nu(m)$ and consider two cases:

If $k>l$ then $2^{l+1}\nmid m-2n$ while $2^{l+1}\mid n$, whence $\nu(n)\ne\nu(m-2n)$, as wanted.

If $k<l$ then $2^{k+1}\mid m-2n$ while $2^{k+1}\nmid n$, implying $\nu(n)\ne\nu(m-2n)$ in this case, too.

To complete the proof, we use straightforward induction by $m=\max\{m,n\}$ distinguishing the following cases: $n=0$, $m=n$, $m=2n$, and the "general case" where none of these holds.