Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

In general, if $p=\gcd(m,n)$ then $p=mx+ny$ for some integers $x,y$.

Now, if $d = \gcd(2^m-1,2^n-1)$ then $2^m \equiv 1 \pmod d$ and $2^n \equiv 1\pmod d$ so $$2^p = 2^{mx+ny} = (2^m)^x(2^n)^y \equiv 1 \pmod d$$

So $d\mid 2^p-1$.

On the other hand, if $p\mid m$ then $2^p-1\mid 2^m-1$ so $2^p-1$ is a common factor.

And yes, you can replace $2$ with any $a$.

Suppose $x$, $m$ and $n$ are positive integers with $m$ and $n$ coprime. First let us show that $$r = 1 + x + {x^2} + \ldots + {x^{m - 1}}$$ and $$s = 1 + x + {x^2} + \ldots + {x^{n - 1}}$$ are relatively prime. If $d$ is a common divisor of $r$ and $s$, then $d$ is relatively prime to $x$ because $r$ and $s$ are one more than a multiple of $x$. Let $m$ be greater than $n$ (or vice versa) and consider $$r - s = {x^n} + {x^{n - 1}} + \ldots + {x^{m - 2}} + {x^{m - 1}} = {x^n}(1 + x + \ldots + {x^{m - n - 1}})$$ and notice that $d$ divides $r - s$ and so must be a divisor of $1 + x + \ldots + {x^{m - n - 1}}$. Observe that $m - n$ is relatively prime to both $m$ and $n$, so we can likewise use geometric sums which eventually becomes shorter and shorter until we conclude that $d$ must divide 1 i.e. $d = 1$. Now if we let $$d' = \gcd (m',n')$$ with $m' = md'$ and $n' = nd'$, then $m$ and $n$ are coprime and $${2^{m'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(m - 1)d'}})$$ $${2^{n'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(n - 1)d'}})$$ which are geometric sums with $x = {2^{d'}}$ and we showed that $\gcd (r,s) = 1$. This completes the proof.

Hint $\rm\bmod d\!:\ a^{\large m}\!\equiv 1\equiv a^{\large n}\!\iff order(a)\mid m,n\iff order(a)\mid(m,n)\iff a^{\large (m,n)}\!\equiv 1$

Therefore $\rm\ \ d\mid a^{\large m}\!-1,\,a^{\large n}\!-1$ $\iff$ $\rm\:d\mid a^{\large (m,n)}\!-1,\ \,$ hence $\rm\,\ \ (a^{\large m}\!-1,\,a^{\large n}\!-1)\, =\, a^{\large (m,n)}-1$