Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$ [duplicate]

Solution 1:

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

Solution 2:

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!)

Solution 3:

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