4
$\begingroup$

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.

  • 1
    BTW it is a special case of this one: http://math.stackexchange.com/questions/28449/ba-nb-1na-12011-11-26

4 Answers 4

9

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

  • 0
    brilliant, so easy... \\ @pedia and Brian: Thanks for your anwers, I'm understanding your proofs too :)2011-11-02
8

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?

3

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$

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.