Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$ Prove that if $d$ divides $n$, then $2^d  -1$ divides $2^n  -1$.
Use the identity $x^k  -1 = (x-1)*(x^{k-1}  +  x^{k-2}    + \cdots + x +1)$
 A: EDIT: Here's a visual proof. In binary base, $2^{d}-1 = \underbrace{1\cdots 1}_{d \text{ times}}$, and 
\begin{align*}
2^n-1 &=\underbrace{1\cdots 1}_{n \text{ times}} = \underbrace{\underbrace{1\cdots 1}_{d \text{ times}} \cdots \underbrace{1\cdots 1}_{d \text{ times}}}_{n/d \text{ times}}  \\
                  &=\underbrace{1\cdots 1}_{d \text{ times}}(1+1\underbrace{0\cdots 0}_{d}+1\underbrace{0\cdots 0}_{2d}+\cdots +1\underbrace{0\cdots 0}_{(n/d-1)d}) \\
&=(2^d - 1)(1+2^d + 2^{2d} + \cdots + 2^{(n/d-1)d}) \blacksquare
\end{align*}
Visualization apart, I just used the hint with $x=2^d-1, k= \frac{n}{d}$.
Original proof (it doesn't use the hint):
In general, $\gcd(2^a-1,2^b-1) = 2^{\gcd(a,b)}-1$. When $a|b$ we get your result.
The proof is by applying the Euclidean algorithm to compute $\gcd(a,b)$: Assuming $a\ge b$,
\begin{align*}
\gcd(2^a-1,2^b-1) &=\gcd(2^a - 1 - (2^b-1),2^b-1)=\gcd((2^{a-b}-1)2^b,2^b-1) \\
                  &=\gcd(2^{a-b}-1,2^b-1).
\end{align*}
So the pair $a,b$ is replaced by $b-a,a$. Repeating this ends with the pair $\gcd(a,b),\gcd(a,b)$, so the $\gcd$ is $\gcd(2^{\gcd(a,b)}-1,2^{\gcd(a,b)}-1)=2^{\gcd(a,b)}-1$.
More generally, $\gcd(a^n - 1, a^m-1)=a^{\gcd(n,m)-1}-1$ ($a$ is an integer or a variable!)
A: $(a-b)\mid(a^m-b^m)$ as $a^m-b^m=(a-b)(a^{m-1}+a^{m-2}b+\cdots+ab^{m-2}+b^{m-1})$ as $a^{m-1}+a^{m-2}b+\cdots+ab^{m-2}+b^{m-1}$ is an integer as $a,b$.
If $m=rs, a^m=a^{rs}=(a^r)^s\implies (a^r-b^r)\mid\{(a^r)^s- (b^r)^s\}$
$\{(a^r)^s- (b^r)^s\}=a^{rs}-b^{rs}=a^m-b^m$
A: Let $n=kd$.
Note that $2^n-1=2^{kd}-1=(2^d)^k-1=(2^d-1)((2^d)^{k-1}+(2^d)^{k-2}+....+(2^d)^0)$
