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

Somewhere on Stack Exchange I saw the equation


I had never seen this before, so I started trying to prove it. Without success...

Can anyone explain me (so actually prove) why this equation is true?

And can we say the same when replacing the '$2$' by any integer number '$a$'?

share|cite|improve this question
Let $m\lt n$. We have $2^n-1=2^{n-m}(2^m-1)+(2^{n-m}-1)$. So our $\gcd$ is $\gcd(2^{n-m}-1, 2^m-1)$. Note how this mirrors the Euclidean Algorithm, subtraction version. – André Nicolas Oct 30 '12 at 16:53
Related: – barto Feb 20 '15 at 9:06
up vote 8 down vote accepted

In general, if $p=\gcd(m,n)$ then $p=mx+ny$ for some integers $x,y$.

Now, if $d = \gcd(2^m-1,2^n-1)$ then $2^m \equiv 1 \pmod d$ and $2^n \equiv 1\pmod d$ so $$2^p = 2^{mx+ny} = (2^m)^x(2^n)^y \equiv 1 \pmod d$$

So $d\mid 2^p-1$.

On the other hand, if $p\mid m$ then $2^p-1\mid 2^m-1$ so $2^p-1$ is a common factor.

And yes, you can replace $2$ with any $a$.

share|cite|improve this answer
Thanks, this explains it. It's of course the first part of the proof that was the problem: proving that $d|2^p-1$. – barto Oct 30 '12 at 16:29

Suppose $x$, $m$ and $n$ are positive integers with $m$ and $n$ coprime. First let us show that $$r = 1 + x + {x^2} + \ldots + {x^{m - 1}}$$ and $$s = 1 + x + {x^2} + \ldots + {x^{n - 1}}$$ are relatively prime. If $d$ is a common divisor of $r$ and $s$, then $d$ is relatively prime to $x$ because $r$ and $s$ are one more than a multiple of $x$. Let $m$ be greater than $n$ (or vice versa) and consider $$r - s = {x^n} + {x^{n - 1}} + \ldots + {x^{m - 2}} + {x^{m - 1}} = {x^n}(1 + x + \ldots + {x^{m - n - 1}})$$ and notice that $d$ divides $r - s$ and so must be a divisor of $1 + x + \ldots + {x^{m - n - 1}}$. Observe that $m - n$ is relatively prime to both $m$ and $n$, so we can likewise use geometric sums which eventually becomes shorter and shorter until we conclude that $d$ must divide 1 i.e. $d = 1$. Now if we let $$d' = \gcd (m',n')$$ with $m' = md'$ and $n' = nd'$, then $m$ and $n$ are coprime and $${2^{m'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(m - 1)d'}})$$ $${2^{n'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(n - 1)d'}})$$ which are geometric sums with $x = {2^{d'}}$ and we showed that $\gcd (r,s) = 1$. This completes the proof.

share|cite|improve this answer
"..., so we can likewise use geometric sum which eventually becomes shorter and shorter until we conclude that d must divide 1...". You may mean this: $d|\frac{x^{m-n}-1}{x-1}$. Let $a=m-n$, then we have $d|1+x+...+x^a$ and $d|1+x+...+x^n$, so we can repeat this over and over, letting $b=|n-a|$, ... Right? (Nice alternative solution, but I must confess I prefer Thomas' proof. Anyway, +1) – barto Oct 30 '12 at 16:39

Hint $\rm\ \ mod\ d\!:\ 2^a\equiv 1\equiv 2^b\iff order(2)\,|\,a,b\iff order(2)\,|\,(a,b)\iff 2^{(a,b)}\equiv 1$

Therefore $\rm\ d\,|\,2^a-1,\,2^b-1\:$ $\iff$ $\rm\:d\,|\,2^{(a,b)}-1,\ \,$ hence $\rm\, \ (2^a-1,\,2^b-1)\, =\, 2^{(a,b)}-1.$

share|cite|improve this answer

Yes, you can say the same when replacing $2$ with an integer $a \geqslant 2$.

Lemma. Suppose that $a \geqslant 2$, $m, n \in \mathbb{N}$ and $\gcd(m, n)=1$. Then $\gcd(a^m-1, a^n-1)=a-1$.

Proof. It is obvious that $(a-1) | \gcd(a^m-1, a^n-1)$. So, we only need to prove that $\gcd(a^m-1, a^n-1) | (a-1)$.

It is well known that if $\gcd(m, n)=1$, then there exist $k, l \in \mathbb{N}$ such that $mk-nl=1$. If is obvious that $(a^n-1)|(a^{nl}-1)$, therefore $$ \gcd(a^m-1, a^n-1) | (a^{nl}-1), $$ and for the same reason $$ \gcd(a^m-1, a^n-1) | (a^{mk}-1). $$

Now we just observe that $$ (a^{mk}-1)-a\cdot(a^{nl}-1) = (a^{nl+1}-1)-(a^{nl+1}-a) = a - 1, $$ therefore $$ \gcd(a^m-1, a^n-1) | (a-1), $$ QED.

Now we can prove the main statement: for $b \geqslant 2$ we have: $$ \gcd(b^m-1, b^n-1) = b^{\gcd(m,n)}-1. $$ Proof. Set $a = b^{\gcd(m, n)}$, $m'=m/\gcd(m,n)$ and $n'=n/\gcd(m,n)$. Clearly, $\gcd(m',n')=1$, and by the lemma we have $$ \gcd(a^{m'}-1,a^{n'}-1) = a-1, $$ which is exactly what we need, QED.

share|cite|improve this answer

let (m,n)=p, then p|m, and p|n, then $m=m_1p$, $n=n_1p$, $(m_1,n_1)=1$, then $(2^{m_1p}-1,2^{n_1p}-1)=((2^{p})^{m_1}-1,(2^{p})^{n_1}-1)=((2^{p}-1)(.....),(2^{p}-1)(.....))=(2^{p}-1)$

share|cite|improve this answer
I don't understand the last step. Why can't $(...)$ and $(...)$ have a common divisor? (I do know what the dots mean) – barto Oct 30 '12 at 16:12
The dots are an unspecified polynomial, which is the remainder after factorising out $2^p-1$. They cannot have a common divisorsince otherwise $(m_1, n_1) \neq 0$ (i.e. we could factorise the power of 2 again). – Simon Hayward Oct 30 '12 at 16:15
So it is a polynomial of the form $2^{m_1}+(\text{lower order terms})$ – Simon Hayward Oct 30 '12 at 16:21
You've only shown that $2^p-1$ is a common factor, not the greatest common factor. – Thomas Andrews Oct 30 '12 at 16:22
How do you know that there are no other common factors? You've just asserted without proof that the terms in the ellispes ($\dots$) have no common factor. – Thomas Andrews Oct 30 '12 at 17:59

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.