Distinct Mersenne numbers are coprime

Question

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

Answer 1

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.