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 

One way to deal with your particular step is to show that $\gcd(x^{a} -1, x^{b} - 1) = x - 1$, when $\gcd(a, b) = 1$. (Actually, a slight variation on the same argument would yield a proof of your original statement, but still.)
Assume $a \ge b \ge 0$, and proceed by induction on $b$. The case $b = 0$ being obvious, assume $b > 0$, divide $a$ by $b$ obtaining $a = q b + r$, with $0 \le r < b$, and note that
$$
x^{a} - 1 = x^{b q + r} - 1 = x^{b q} x^{r} - 1 \equiv x^{r} - 1 \pmod{x^{b} - 1}.
$$
Therefore $\gcd(x^{a} -1, x^{b} - 1) = \gcd(x^{b} -1, x^{r} - 1)$, which is $x - 1$ by the inductive hypothesis, as $1 = \gcd(a, b) = \gcd(b, r)$.
