# Distinct Mersenne numbers are coprime

How can you prove that if $p$ and $q$ are distinct primes, then the following holds?:

$$(M_p,M_q)=1$$

Note: $M_n=2^n-1$, with $n$ prime number

• What's the $(\ .\ ,\ .\ )$ notation? GCD? – Jack M Oct 3 '13 at 22:31
• @JackM Yes, it is GCD. – marcelolpjunior Oct 3 '13 at 22:33
• The title is now possibly misleading: if we use the Wikipedia definition of a Mersenne number as any number $2^n-1$ (with no requirement for $n$ to be prime), then the result is clearly false. Should we say "distinct pernicious Mersenne nunbers are coprime"? – Old John Oct 3 '13 at 23:09
• – lab bhattacharjee Oct 4 '13 at 18:17

## 2 Answers

Let $z < x < y$ all be integers with $y = kx + z$ for some positive integer $k$.

I claim that $2^y - 1 \equiv 2^z - 1 \pmod{2^x - 1}$.

Proof:

$(2^y - 1) - 2^{y-x}(2^x - 1) = 2^y - 1 - 2^y + 2^{y-x} = 2^{y-x} - 1$, so

$2^y - 1 \equiv 2^{y-x} - 1 \pmod{2^x-1}$. By similar reasoning, it is also congruent to $2^{y-2x} - 1, 2^{y-3x} - 1, \ldots, 2^{y-kx} - 1 = 2^z - 1$.

Hence, $\gcd(2^y - 1, 2^x - 1) = \gcd(2^x - 1, 2^z - 1)$, and you can iterate this to decrease the exponents in a way similar to the numbers in the Euclidean algorithm. I trust you can take it from here.

Since $\gcd(a^n-1, a^m-1) =a^{\gcd(n, m)}-1$ (see $\gcd(b^x - 1, b^y - 1, b^ z- 1,...) = b^{\gcd(x, y, z,...)} -1$), $\gcd(a^p-1, a^q-1) =a^{\gcd(p, q)}-1 =a-1$ since distinct primes are coprime.