# Proof that $\gcd(2^m-1,2^n+1)=1$ for odd $m$ using group theory

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.

• I gave an answer here based on group theory. The later answer below by Alex W uses exactly the same argument – 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$.
• 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$. – Alex W May 12 '15 at 5:44
• @StVincent Yes. $\bar x=\phi(x)$. – Alex W May 12 '15 at 5:49
• I thought $\phi(d)$ was the order of $\mathbb{Z}/(d)?$ – St Vincent May 12 '15 at 6:07
• 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)$. – Alex W May 12 '15 at 6:10