Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

4 Answers

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|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
add comment

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|improve this answer
add comment

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$

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.