number theory - Greatest common divisor of $(2^{21}-1,2^{27}-1)$

Find $\text{gcd}(2^{21}-1,2^{27}-1).$

My proof: We know that $2^{21}-1=(2^3)^7-1=8^7-1=(8-1)(8^6+\dots+8+1)=7(8^6+\dots+8+1)=7N_1$ and $2^{27}-1=(2^3)^9-1=8^9-1=(8-1)(8^8+\dots+8+1)=7(8^8+\dots+8+1)=7N_2.$ Also $N_2-N_1=8^8+8^7$. Hence $$\text{gcd}(2^{21}-1,2^{27}-1)=\text{gcd}(7N_1,7N_2)=7\text{gcd}(N_1,N_2).$$

I guess that $\text{gcd}(N_1,N_2)=1$ but I can't prove rigorously. Can anyone show a full proof?

Answer

We know that $$\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$$
So now $$\gcd(2^{21}-1,2^{27}-1)=2^{\gcd(21,27)}-1=7$$

---

We'll now prove the theorem I used here.

We can do the following. Assume $n>m$, then: $$\begin{align} \gcd(a^n-1,a^m-1)&=\gcd((a^n-1)-(a^m-1),a^m-1)\\ &=\gcd(a^m(a^{n-m}-1),a^m-1)\\ \end{align}$$
since $\gcd(a^m,a^m-1)=1$, we now know
$$\gcd(a^n-1,a^m-1)=\gcd(a^{n-m}-1,a^m-1)$$
Now we can do Euclid's algorithm in the exponents! We obtain the final equality $$\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$$