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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Oct 31 '11 at 9:47
  • $\begingroup$ Here is the general case from another question: math.stackexchange.com/questions/7473/… $\endgroup$ – Gbean Oct 31 '11 at 9:54
  • 3
    $\begingroup$ Qiaochu Yuan’s solution of the general case here is probably more readable than those at the question that Gbean found. $\endgroup$ – Brian M. Scott Oct 31 '11 at 10:03
  • $\begingroup$ It may be useful to write $(m,n)$ as $am+bn$ where $a,b$ are integers. $\endgroup$ – Mark Oct 31 '11 at 10:25
  • $\begingroup$ math.stackexchange.com/questions/225289 $\endgroup$ – Bart Michels Feb 21 '15 at 16:30