Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$
my work:
I assumed $m = da$ , $n = db$ for $a,b \in \mathbb{Z}$.
Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. 
similarly
 $2^n - 1$ = $x^b - 1$
Now, 
using $x^a - 1 = (x - 1)(x^{a-1} + x^{a - 2} + .... + x + 1)$ and $x^b - 1 = (x - 1)(x^{b - 1} + x^{b - 2} + ..... + x + 1)$    
clearly $(x - 1)$ is a factor common in both but how to show that
$(x^{a-1} + x^{a - 2} + .... + x + 1)$ and $(x^{b-1} + x^{b - 2} + .... + x + 1)$ can't have a common factor 

If $a=b$ this means you have $m=n=d$ so this is trivial.
Assume now that $a\neq b$, well you can exchange both so that we can always assume $a>b$ :
$$x^{a-b}(x^{b-1}+...+x+1)=x^{a-1}+...+x^{a-b+1}+x^{a-b} $$
Hence :
$$x^{a-1}+...+x+1-x^{a-b}(x^{b-1}+...+x+1)=x^{a-b-1}+...+x+1 $$
It implies that $\gcd(x^{a-1}+...+x+1,x^{b-1}+...+1)$ divides $\gcd(x^{a-b-1}+...+x+1,x^{b-1}+...+1)$. Furthermore $\gcd(a-b,b)=\gcd(a,b)=1$. This is the heridity of an induction on $N$ :
$$\text{ for all integers } 1\leq a,b\leq N \text{ with } \gcd(a,b)=1 \text{ we have : } $$ 
$$\gcd(x^{a-1}+...+x+1,x^{b-1}+...+1)=1$$ 
