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.

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$.

Use the identity $x^k -1 = (x-1)*(x^{k-1} + x^{k-2} + \cdots + x +1)$

share|improve this question
add comment

3 Answers 3

Let $n=kd$.

Note that $2^n-1=2^{kd}-1=(2^d)^k-1=(2^d-1)((2^d)^{k-1}+(2^d)^{k-2}+....+(2^d)^0)$

share|improve this answer
    
+1 for the explicit use of the suggested approach. –  Dilip Sarwate Dec 27 '12 at 16:49
add comment

$(a-b)\mid(a^m-b^m)$ as $a^m-b^m=(a-b)(a^{m-1}+a^{m-2}b+\cdots+ab^{m-2}+b^{m-1})$ as $a^{m-1}+a^{m-2}b+\cdots+ab^{m-2}+b^{m-1}$ is an integer as $a,b$.

If $m=rs, a^m=a^{rs}=(a^r)^s\implies (a^r-b^r)\mid\{(a^r)^s- (b^r)^s\}$

$\{(a^r)^s- (b^r)^s\}=a^{rs}-b^{rs}=a^m-b^m$

share|improve this answer
add comment

EDIT: Here's a visual proof. In binary base, $2^{d}-1 = \underbrace{1\cdots 1}_{d \text{ times}}$, and

\begin{align*} 2^n-1 &=\underbrace{1\cdots 1}_{n \text{ times}} = \underbrace{\underbrace{1\cdots 1}_{d \text{ times}} \cdots \underbrace{1\cdots 1}_{d \text{ times}}}_{n/d \text{ times}} \\ &=\underbrace{1\cdots 1}_{d \text{ times}}(1+1\underbrace{0\cdots 0}_{d}+1\underbrace{0\cdots 0}_{2d}+\cdots +1\underbrace{0\cdots 0}_{(n/d-1)d}) \\ &=(2^d - 1)(1+2^d + 2^{2d} + \cdots + 2^{(n/d-1)d}) \blacksquare \end{align*}

Visualization apart, I just used the hint with $x=2^d-1, k= \frac{n}{d}$.

Original proof (it doesn't use the hint):

In general, $\gcd(2^a-1,2^b-1) = 2^{\gcd(a,b)}-1$. When $a|b$ we get your result.

The proof is by applying the Euclidean algorithm to compute $\gcd(a,b)$: Assuming $a\ge b$,

\begin{align*} \gcd(2^a-1,2^b-1) &=\gcd(2^a - 1 - (2^b-1),2^b-1)=\gcd((2^{a-b}-1)2^b,2^b-1) \\ &=\gcd(2^{a-b}-1,2^b-1). \end{align*}

So the pair $a,b$ is replaced by $b-a,a$. Repeating this ends with the pair $\gcd(a,b),\gcd(a,b)$, so the $\gcd$ is $\gcd(2^{\gcd(a,b)}-1,2^{\gcd(a,b)}-1)=2^{\gcd(a,b)}-1$.

More generally, $\gcd(a^n - 1, a^m-1)=a^{\gcd(n,m)-1}-1$ ($a$ is an integer or a variable!)

share|improve this answer
1  
Hi Ofir. I edited the long equation in your answer with align to make it smooth and easier to read. You can also take a look and see how it works if you like it. –  Thomas E. Dec 27 '12 at 15:33
    
@ThomasE. - Thanks, I learnt something new and even used it again (see the new solution). –  Ofir Dec 27 '12 at 16:34
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.