Proof: If $n=ab$ then $2^a-1 \mid 2^n-1$ I don't know how to explain or how to prove the following statement
If $n=ab$ and $a,b \in \mathbb{N}$ then $2^a-1 \mid 2^n-1$.
Any ideas? Perhaps an induction?
Thanks in advance.
 A: Hint:  Recall that $$x^u-1=(x-1)(x^{u-1}+x^{u-2}+\cdots+x+1).$$  Then $$2^{ab}-1 =(2^a)^b-1$$ and letting $x=2^a$, $u=b$ we see that
$$(2^a)^b-1=(2^a-1)\left((2^a)^{b-1}+(2^a)^{b-2}+\cdots+(2^a)+1\right).$$  This means that $2^a-1$ must divide it.  We can use a similar argument for $2^b-1$.
A: HINT: Write $2^a-1$ and $2^n-1$ in binary notation: the first is a string of $a$ $1$’s, and the second is a string of $n$ $1$’s. Now think about doing an ordinary long division, still in base two. Can you see why there will be no remainder?
A: In order to prove this we have to apply following identity (see bottom of this page):
$\gcd(2^p-1,2^q-1)=2^{\gcd(p,q)}-1$
So we may write:
$\gcd(2^a-1,2^{ab}-1)=2^{\gcd(a,ab)}-1=2^{a}-1\Rightarrow 2^a-1 \mid 2^n-1$
A: HINT $\rm\ \ mod\ 2^A-1\!:\ \ 2^A\equiv 1\ \Rightarrow\ 2^{AB}\equiv (2^A)^B\equiv\ 1^B\equiv 1\ \ $ QED 
So it is just a special case of $\rm\ C\equiv 1\ \Rightarrow\ C^N\equiv 1\:.\: $ Notice in particular how the use of congruences enabled us convert a not immediately obvious propery of a relation (divisibility) to an immediately obvious property of a function (multiplication operation).  The reason for such spectacular success will become clearer when you study congruences and ideals in ring theory. See also here.
