# Show that $\gcd(2^m-1, 2^n-1) = 2^ {\gcd(m,n)} -1$ [duplicate]

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.

-

## marked as duplicate by joriki, anon, Jyrki Lahtonen♦, Henning Makholm, Asaf KaragilaOct 31 '11 at 10:34

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
It may be useful to write $(m,n)$ as $am+bn$ where $a,b$ are integers. –  Mark Oct 31 '11 at 10:25