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.

Possible Duplicate:
Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$
$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$

I'm trying to figure this out:

Show that for all positive integers $m$ and $n$

$\gcd(2^m-1, 2^n-1) = 2^{\gcd(m,n)} -1$

I appreciate your help, Thanks.

Note: $\gcd$ stands for the greatest common divisor.

share|improve this question

marked as duplicate by joriki, anon, Jyrki Lahtonen, Henning Makholm, Asaf Karagila Oct 31 '11 at 10:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Can you at least show that $2^{\gcd(m,n)}-1$ is a common divisor of $2^m-1$ and $2^n-1$? That’s actually fairly easy to see if you write all three numbers in binary. –  Brian M. Scott Oct 31 '11 at 9:47
    
Here is the general case from another question: math.stackexchange.com/questions/7473/… –  Gbean Oct 31 '11 at 9:54
3  
Qiaochu Yuan’s solution of the general case here is probably more readable than those at the question that Gbean found. –  Brian M. Scott Oct 31 '11 at 10:03
    
It may be useful to write $(m,n)$ as $am+bn$ where $a,b$ are integers. –  Mark Oct 31 '11 at 10:25