1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What's the $(\ .\ ,\ .\ )$ notation? GCD? $\endgroup$ – Jack M Oct 3 '13 at 22:31
  • $\begingroup$ @JackM Yes, it is GCD. $\endgroup$ – marcelolpjunior Oct 3 '13 at 22:33
  • $\begingroup$ 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"? $\endgroup$ – Old John Oct 3 '13 at 23:09
  • $\begingroup$ Related : math.stackexchange.com/questions/7473/… $\endgroup$ – lab bhattacharjee Oct 4 '13 at 18:17
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.