Find the greatest common divisor of $2^m+1$ and $2^n+1$ that $m,n$ are positive integers. I am confused of a question that needs to know the greatest common divisor of $2^m+1$ and $2^n+1$ ($m,n$ are positive integers), but I don't really know. I am pretty sure that the greatest common divisor of $2^m-1$ and $2^n-1$ ($m,n$ are positive integers) is $2^{\gcd\left(m,n\right)}-1$, even I can prove it by the Euclidean algorithm. However, it is hard to use it in this problem, so I want you guys to help me. Thanks!
P.S.
I created an excel and I observed the answer (maybe?) from it, but I can't prove or disprove it. Here is my conclusion from the excel:
$$\gcd\left(2^m+1,2^n+1\right)=\begin{cases} 2^{\gcd\left(m,n\right)}+1 \\ 1 \end{cases}\begin{matrix} \text{when }m,n\text{ contain the exact same power of }2 \\ \text{otherwise} \end{matrix}$$
Hope it will help me and you guys solving this quesion :D
The link of The excel

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.
