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.

Somewhere on Stack Exchange I saw the equation $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$ 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|improve this question
    
Indeed, we can say the same when replacing $2$ by $a$. –  barto Oct 30 '12 at 16:45
1  
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
add comment

5 Answers

up vote 3 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|2^p-1$.

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

share|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
add comment

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|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
add comment

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|improve this answer
    
Thanks. The equivalence-arrows are indispensable, indeed. –  barto Feb 10 '13 at 13:16
add comment

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|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
    
Really? Even though there are no further common factors in the remainder? –  Simon Hayward Oct 30 '12 at 16:23
show 4 more comments

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|improve this answer
    
+1 for another original proof. –  barto Oct 30 '12 at 17:06
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.