Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
+1 for the explicit use of the suggested approach. – Dilip Sarwate Dec 27 '12 at 16:49

$(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|cite|improve this answer

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|cite|improve this answer
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. – T. Eskin 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

Your Answer


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.