# 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?

-
BTW it is a special case of this one: math.stackexchange.com/questions/28449/ba-nb-1na-1 – Martin Sleziak Nov 26 '11 at 16:54

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$.

-
brilliant, so easy... \\ @pedia and Brian: Thanks for your anwers, I'm understanding your proofs too :) – ulead86 Nov 2 '11 at 11:11

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?

-

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$

-

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.

-