Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

This question was marked as an exact duplicate of an existing 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:… – Gbean Oct 31 '11 at 9:54
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