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 😀
The link of The excel
Best Answer
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.