Distinct Mersenne numbers are relatively prime specific proof verification

Question

As the title states, I'm supposed to prove for distinct primes $p_1,p_2 >2$ the primes dividing $2^{p_1}-1$ and $2^{p_2}-1$ are distinct.

The Wikipedia page on Theorems about Mersenne Numbers states that #6: if $m$ and $n$ are natural numbers then $m$ and $n$ are coprime if and only if $2^m-1$ and $2^n-1$ are coprime, the only one without proof. I believe I have to prove the forward $(\Longrightarrow)$ direction.

---

edit: this was my own work for a homework question, and I was mainly wondering if the proof was okay. there is no proof directly provided on Wikipedia, and I didn’t find the links to the proof the clearest either. this was the clearest proof to me at the time and wanted someone else’s feedback because I couldn’t believe my proof was right.

---

My attempt at a proof (I use $a,b$ instead of $p_1,p_2$ or $m,n$):

Suppose $(a,b)=1$ and $(2^a - 1, 2^b -1) = d$.

Since $(a,b)=1$ there exist $x,y \in \mathbb{Z}$ s.t. $ax+by=1$.

Since $a,b > 2$, $x$ and $y$ cannot both be greater than zero, otherwise $ax+by > 2+2 >1$. Neither can $x$ or $y$ be equal to zero, otherwise $x$ or $y$ would $\not\in\mathbb{Z}$, or $ax+by=0\not=1$. Neither can $x$ and $y$ be less than zero, otherwise then $ax+by <0<1$.

Thus one of $x$ or $y$ must be positive, while the other negative.

Suppose $ax>0$ then $by<0$, then $d|2^{ax}-1$ and $d|2^{-by}-1$ since

$$2^{ax}-1 = (2^a -1)((2^a)^{x-1}+(2^a)^{x-2}+\cdots+1)$$

$$2^{-by}-1 = (2^b -1)((2^b)^{-y-1}+(2^b)^{-y-2}+\cdots+1)$$

and $d|2^a -1$ and $d|2^b -1$ by definition. Then $2^{ax} - 1 = d\alpha$ and $2^{-by} -1 = d\beta$ and then $2^{ax}-2^{-by} = 2^{-by}(2^{ax+by}-1)=2^{-by}(2^1-1)=2^{-by} = d(\alpha -\beta)$ thus $d|2^{-by}$ and $d$ must be a power of $2$. But $d|2^a-1$ where $2^a-1$ is odd, and the only odd power of $2$ is $2^0=1$, hence $d=1$. If $(a,b)=1$ then $(2^a -1 ,2^b-1)=d=1$.

Is my proof rigorous or am I missing something?

Answer 1

Your proof is fine, though you might also need to mention the case $ax < 0$ and $by > 0$ (though immediate).

By Wikipedia standards, most theorems are accompanied by a proof, or if not possible, a reference to the proof would be provided. In this case, the statement of this theorem is accompanied with a "[20]", which links to an archived version of Will Edgington's Mersenne Page. The various Lemmas in the section Mersenne Number Proofs supplies a proof to the claim.

Discussions on MSE that are also useful include:

• Distinct Mersenne numbers are coprime

• Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

Answer 2

Looks rigorous enough. But there's a more elementary proof with a slightly more general definition of Mersenne numbers( where exponents are natural numbers):

$$2(2^n-1)+1=2^{n+1}-1$$ since $$2^1-1=1$$ is a sequence member, iteration produces the general recurrence :$$2^{n+m}-1=2^m(2^n-1)+(2^m-1)$$ This means for two Mersennes to share a factor, the Mersenne with exponent their difference in exponent must share it.

Euclidean gcd is based on taking the difference of two values, and saying the gcd must be a factor. But, applying that in the exponent repeatedly, gives us the fact that two coprime exponent Mersenne numbers, can only share a factor if: $$2^1-1=1$$ shares it. Therefore they can only share the factor 1.