<s>[INST] 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)$
 [/INST] 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!)
</s>