Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
BTW it is a special case of this one: – Martin Sleziak Nov 26 '11 at 16:54
up vote 9 down vote accepted

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

share|cite|improve this answer
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?

share|cite|improve this answer

In order to prove this we have to apply following identity (see bottom of this page):


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$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.