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