Below is a perfectly fine proof using basic tools of number theory:

Showing $\gcd(2^m-1,2^n+1)=1$

Could we prove this more quickly using group theory? I would be very interested in seeing an abstract algebra-flavored proof.

  • $\begingroup$ I gave an answer here based on group theory. The later answer below by Alex W uses exactly the same argument $\endgroup$ – Bill Dubuque Jan 1 '19 at 19:29

Let $d=\gcd(2^m-1,2^n+1)$ and $\phi:\mathbb Z\to \mathbb{Z}/(d)$ be the natural homomorphism of rings. We will use a bar convention. Since $d\mid 2^m-1$, then $0=\overline{2^m-1}={\bar 2}^m-1$, i.e. $\bar 2^m=1$. Similarly, $\bar 2^n=-1$. It follows, that $\bar 2\in(\mathbb{Z}/(d))^*$, where $(\mathbb{Z}/(d))^*$ - group of invertible elements of $\mathbb{Z}/(d)$. Since $\bar 2^n=-1$, then $\bar 2^{2n}=1$. So, $\bar 2^m=1$ and $\bar 2^{2n}=1$, hence $|\bar 2|\mid m$ and $|\bar 2|\mid 2n$, i.e. $|\bar 2|\mid\gcd(m,2n)$. Since $m$ odd, then $\gcd(m,2n)=\gcd(m,n)$, therefore $\bar 2^m=1$, $\bar 2^n=1$. But $\bar 2^n=-\bar 1$, hence $\bar 1=-\bar 1$. It follows that $\bar 2=0$, i.e. $d\mid 2$. But, obviously, $d$ is odd, hence $d=1$.

| cite | improve this answer | |
  • $\begingroup$ Using similar argument's it can be proved, for example, that $\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$ for any natural $m,n$ and $a>1$. $\endgroup$ – Alex W May 12 '15 at 5:44
  • $\begingroup$ The overline is used to denote congruence classes? $\endgroup$ – St Vincent May 12 '15 at 5:48
  • $\begingroup$ @StVincent Yes. $\bar x=\phi(x)$. $\endgroup$ – Alex W May 12 '15 at 5:49
  • $\begingroup$ I thought $\phi(d)$ was the order of $\mathbb{Z}/(d)?$ $\endgroup$ – St Vincent May 12 '15 at 6:07
  • $\begingroup$ I prefer to denote Euler totient function $\varphi(d)$. Then $\varphi(d)=|(\mathbb Z/(d))^*|$ - order of a group of invertible elements of $\mathbb Z/(d)$. $\endgroup$ – Alex W May 12 '15 at 6:10

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.