A question regarding the proof of $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$ I have a problem trying to understand the proof:

Theorem $\boldsymbol{1.1.5.}$ For natural numbers $a,m,n$, $\gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$

Outline. Note that by the Euclidean Algorithm, we have
$$
\begin{align}
\gcd\left(a^m-1,a^n-1\right)
&=\gcd\left(a^m-1-a^{m-n}\left(a^n-1\right),a^n-1\right)\\
&=\gcd\left(a^{m-n}-1,a^n-1\right)
\end{align}
$$
original image
We can continue to reduce the exponents using the Euclidean Algorithm, until we ultimately have $\gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$. $\square$
I see that the next iteration (if possible) is $\gcd(a^{m-2n}, a^n-1)$. However, why is the conclusion is true by euclidean algorithm?
 A: Let $a,m,n$ be positive integers, $a>1$. Then
$$ \gcd(a^m-1,a^n-1) = a^{\gcd(m,n)}-1. $$
Write $g=\gcd(a^m-1,a^n-1)$. Suppose $m=qn+r$, $0 \le r <n$. From $g \mid (a^n-1)$ we have $g \mid (a^{qn}-1)$. Therefore,
$$ g \mid \big((a^m-1)-a^r(a^{qn}-1)\big) = (a^r-1). $$
Therefore, $g \mid \gcd(a^n-1,a^r-1)$. We have deduced this analogous to deducing $\gcd(m,n) \mid \gcd(n,r)$ in Euclid's algorithm to find $\gcd(m,n)$.
Suppose the steps in Euclid's algorithm are as follows:
\begin{eqnarray*}
m & = & qn+r, \: 0<r<n, \\ 
n & = & q_1r + r_1, \: 0 < r_1 < r, \\
r & = & q_2r_1 + r_2, \: 0 < r_2 < r_1, \\ 
\vdots & = & \vdots \\
r_{k-2} & = & q_kr_{k-1} + r_k, \: 0 < r_k < r_{k-1}, \\ 
r_{k-1} & = & q_{k+1}r_k. 
\end{eqnarray*}
Using the same argument repeatedly leads to $g \mid \gcd(a^{r_{k-1}}-1,a^{r_k}-1)$, and since $r_k \mid r_{k-1}$, to $g \mid (a^{r_k}-1) = (a^{\gcd(m,n)}-1)$.
Conversely, $\gcd(m,n)$ divides both $m$ and $n$, and so $a^{\gcd(m,n)}-1$ divides both $a^m-1$ and $a^n-1$. But then $a^{\gcd(m,n)}-1$ divides $g$.
This completes the proof. $\blacksquare$
A: Suppose :
$gcm(m, n)= k$
$m=m_1 k$
$n=n_1 k$
Then we have:
$a^m-1=(a^K)^{m_1}-1=(a^k-1)[(a^k)^{m_1-1}+(a^k)^{m_1-2}+ . . . $
$a^n-1=(a^K)^{n_1}-1=(a^k-1)[(a^k)^{n_1-1}+(a^k)^{n_1-2}+ . . . $
That means:
$gcd(a^m-1, a^n-1)=a^k-1=a^{gcm(m, n)}-1$
Notice that the factor $(a^k-1)$ exists for both cases where m and n are both odd or even.
