3
$\begingroup$

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.

  • 0
    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.2011-10-31
  • 0
    Here is the general case from another question: http://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-12011-10-31
  • 3
    Qiaochu Yuan’s solution of the general case [here](http://math.stackexchange.com/questions/11567/gcdbx-1-by-1-b-z-1-b-gcdx-y-z-1/11570#11570) is probably more readable than those at the question that Gbean found.2011-10-31
  • 0
    It may be useful to write $(m,n)$ as $am+bn$ where $a,b$ are integers.2011-10-31
  • 0
    http://math.stackexchange.com/questions/2252892015-02-21

0 Answers 0