Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ For all $a, m, n \in \mathbb{Z}^+$, 
$$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
 A: Mimic in expts a subtractive Euclidean algorithm $\rm\,(n,m) = (\color{#0a0}{n\!-\!m},m)$
$$\begin{align} \rm{e.g.}\ \ &\rm (f_5,f_2) = (f_3,f_2) = (f_1,f_2) = (f_1,f_1) = (f_1,\color{darkorange}{f_0})= f_1 = f_{\:\!(5,\,2)}\\[.3em]
{\rm like}\ \ \ &(5,\ 2)\, =\:\! (3,\ 2)\, =\:\! (1,\ 2)\:\! =\:\! (1,\ 1)\:\! =\:\! (1,\ \color{darkorange}0)\:\! = 1,\ \ {\rm since}\end{align}\qquad$$
$\rm\ f_{\,n}\: :=\ a^n\!-\!1\ =\ a^{n-m} \: \color{#c00}{(a^m\!-\!1)} + \color{#0a0}{a^{n-m}\!-\!1},\,\ $  hence $\rm\:\ {f_{\,n}\! = \color{#0a0}{f_{\,n-m}}\! + k\ \color{#c00}{f_{\,m}}},\,\ k\in\mathbb Z,\:$  thus
Theorem $\: $ If $\rm\ f_{\, n}\: $ is an integer sequence with $\rm\ \color{darkorange}{f_{0} =\, 0},\: $ $\rm \:{ f_{\,n}\!\equiv \color{#0a0}{f_{\,n-m}}\ (mod\ \color{#c00}{f_{\,m})}}\ $ for all $\rm\: n > m,\ $  then $\rm\: (f_{\,n},f_{\,m})\ =\ f_{\,(n,\:m)}, \: $ where $\rm\ (i,\:j)\ $ denotes $\rm\ gcd(i,\:j).\:$
Proof $\ $ By induction on  $\rm\:n + m\:$. The theorem is trivially true if $\rm\ n = m\ $ or $\rm\ n = \color{darkorange}0\ $ or $\rm\: m = \color{darkorange}0.\:$
So we may assume $\rm\:n > m > 0\:$.$\ $  Note $\rm\ (f_{\,n},f_{\,m}) = (\color{#0a0}{f_{\,n-m}},\color{#c00}{f_{\,m}})\ $ follows by $\rm\color{#90f}{Euclid}$ & hypothesis.
Since $\rm\ (n-m)+m \ <\ n+m,\ $ induction yields $\rm\, \ (f_{\,n-m},f_{\,m})\, =\, f_{\,(n-m,\:m)} =\, f_{\,(n,\:m)}.$
$\rm\color{#90f}{Euclid}\!:\ A\equiv a\pmod{\! m}\,\Rightarrow\ (A,m) = (a,m)\,$ is the reduction (descent) step used both above and in the Euclidean algorithm $\rm\: (A,m) = (A\bmod m,\,m),\, $ the special case $\,\rm f_{\:\!n} = n\,$ above.
This is a prototypical strong divisibility sequence. Same for Fibonacci numbers.

Alternatively it has a natural proof via the Order Theorem $\ a^k\equiv 1\iff {\rm ord}(a)\mid k,\,$ viz.
$$\begin{eqnarray}\ {\rm mod}\:\ d\!:\  a^M\!\equiv 1\equiv a^N&\!\iff\!& {\rm ord}(a)\ |\ M,N\!\color{#c00}\iff\! {\rm ord}(a)\ |\ (M,N)\!\iff\! \color{#0a0}{a^{(M,N)}\!\equiv 1}\\[.2em]
 {\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1\! &\!\iff\!\!&\ d\ |\ \color{#0a0}{a^{(M,N)}\!-\!1},\qquad\,\ {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N)
\end{eqnarray}\ \ \ \ \ $$
Thus, by above $\, a^M\!-\!1,\:a^N\!-\!1\ $ and $\, a^{(M,N)}\!-\!1\ $  have the same set $\,S\,$ of common divisors $\,d,\, $ therefore they have the same greatest common divisor $\ (= \max\ S).$
Note $ $ We  used the GCD universal property $\ a\mid b,c \color{#c00}\iff a\mid (b,c)\ $ [which is the definition of a gcd in more general rings]. $ $ Compare that with $\ a<b,c \!\iff\! a< \min(b,c),\, $ and, analogously, $\,\  a\subset b,c\iff a\subset b\cap c.\ $ Such universal "iff" characterizations enable quick and easy simultaneous proof of both directions.
The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See this answer for more on this and the more familiar additive form of a denominator ideal.
A: Written for a duplicate question, this may be a bit more elementary than the other answers here, so I will post it:

If $g=(a,b)$ and $G=\left(p^a-1,p^b-1\right)$, then
$$
\left(p^g-1\right)\sum_{k=0}^{\frac ag-1}p^{kg}=p^a-1\tag1
$$
and
$$
\left(p^g-1\right)\sum_{k=0}^{\frac bg-1}p^{kg}=p^b-1\tag2
$$
Thus, we have that
$$
\left.p^g-1\,\middle|\,G\right.\tag3
$$

For $x\ge0$,
$$
\left(p^a-1\right)\sum_{k=0}^{x-1}p^{ak}=p^{ax}-1\tag4
$$
Therefore, we have that
$$
\left.G\,\middle|\,p^{ax}-1\right.\tag5
$$
If $\left.G\,\middle|\,p^{ax-b(y-1)}-1\right.$, then 
$$
\left.G\,\middle|\,\left(p^{ax-b(y-1)}-1\right)-p^{ax-by}\left(p^b-1\right)\right.=p^{ax-by}-1\tag6
$$
Therefore, by induction on $y$ (with $(5)$ as the base case and $(6)$ as the inductive step), for any $x,y\ge0$ so that $ax-by\ge0$,
$$
\left.G\,\middle|\,p^{ax-by}-1\right.\tag7
$$
which means that
$$
\left.G\,\middle|\,p^g-1\right.\tag8
$$

Putting all this together gives
$$
G=p^g-1\tag9
$$
A: Below is a proof which has the neat feature that it immediately specializes
to a proof of the integer Bezout identity for $\rm\:x = 1,\:$ allowing us to view it as a q-analog of the integer case.
E.g. for $\rm\ m,n\ =\ 15,21$
$\rm\displaystyle\quad\quad\quad\quad\quad\quad\quad \frac{x^3-1}{x-1}\ =\ (x^{15}\! +\! x^9\! +\! 1)\ \frac{x^{15}\!-\!1}{x\!-\!1} - (x^9\!+\!x^3)\ \frac{x^{21}\!-\!1}{x\!-\!1}$
for  $\rm\ x = 1\ $  specializes to  $\ 3\ \ =\  \ 3\ (15)\ \ -\ \ 2\ (21)\:,\ $ i.e. $\rm\ (3)\ =\ (15,21) := gcd(15,21)$
Definition $\rm\displaystyle \quad n' \: :=\ \frac{x^n - 1}{x-1}\:$. $\quad$ Note $\rm\quad  n' = n\ $  for  $\rm\ x = 1$.
Theorem $\rm\quad (m',n')\ =\ ((m,n)')\ $ as ideals in $\rm\,\Bbb Z[x],\,$for naturals $\rm\:m,n.$
Proof $\ $ It is trivially true if $\rm\ m = n\ $  or  if  $\rm\ m = 0\ $  or  $\rm\ n = 0.\:$
W.l.o.g. suppose  $\rm\:n > m > 0.\:$ We proceed by induction on  $\rm\:n\! +\! m.$
$\begin{eqnarray}\rm   &\rm x^n\! -\! 1 &=&\ \rm  x^r\ (x^m\! -\! 1)\  +\  x^r\! -\! 1 \quad\ \ \rm for\ \  r = n\! -\! m \\  
\quad\Rightarrow\quad &\rm\qquad n' &=&\ \rm  x^r\ m'\ +\ r' \quad\ \ \rm by\ dividing\ above\ by\ \ x\!-\!1 \\
\quad\Rightarrow\ \  &\rm  (m', n')\, &=&\ \ \rm (m', r') \\
 & &=&\rm   ((m,r)') \quad\ \ by\ induction, applicable\ by\:\  m\!+\!r = n < n\!+\!m \\
 & &=&\rm   ((m,n)') \quad\ \ by\ \  r \equiv n\ \:(mod\ m)\quad\ \ \bf QED
\end{eqnarray}$
Corollary $\ $ Integer Bezout Theorem $\ $ Proof: $ $ set $\rm\ x = 1\ $ above, i.e. erase primes.
A deeper understanding comes when one studies Divisibility Sequences
and Divisor Theory.
A: Let $m\ge n\ge 1$. Apply Euclidean Algorithm.
$\gcd\left(a^m-1,a^n-1\right)=\gcd\left(a^{n}\left(a^{m-n}-1\right),a^n-1\right)$. Since $\gcd(a^n,a^n-1)=1$, we get
$\gcd\left(a^{m-n}-1,a^n-1\right)$. Iterate this until it becomes $$\gcd\left(a^{\gcd(m,n)}-1,a^{\gcd(m,n)}-1\right)=a^{\gcd(m,n)}-1$$
A: Let
$$\gcd(a^n - 1, a^m - 1) = t$$
then
$$a^n \equiv 1 \pmod t\,\quad\text{and}\quad\,a^m \equiv 1 \,\pmod t$$
And thus
$$a^{nx + my} \equiv 1\, \pmod t$$
$\forall\,x,\,y\in \mathbb{Z}$
According to the Extended Euclidean algorithm, we have
$$nx + my =\gcd(n,m)$$
This follows
$$a^{nx + my} \equiv 1\pmod t \implies a^{\gcd(n,m)} \equiv 1 \pmod t\implies  t\big|\big( a^{\gcd(n,m)} - 1\big) $$
Therefore
$$a^{\gcd(m,n)}-1\, =\gcd(a^m-1, a^n-1) $$
Since it is easy to show $(a^{\gcd(n,m)}-1)\big|t$.
A: More generally, if $\gcd(a,b)=1$, $a,b,m,n\in\mathbb Z^+$, $a> b$, then $$\gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)}$$
Proof: Since $\gcd(a,b)=1$, we get $\gcd(b,d)=1$, so $b^{-1}\bmod d$ exists.
$$d\mid a^m-b^m, a^n-b^n\iff \left(ab^{-1}\right)^m\equiv \left(ab^{-1}\right)^n\equiv 1\pmod{d}$$
$$\iff \text{ord}_{d}\left(ab^{-1}\right)\mid m,n\iff \text{ord}_{d}\left(ab^{-1}\right)\mid \gcd(m,n)$$
$$\iff \left(ab^{-1}\right)^{\gcd(m,n)}\equiv 1\pmod{d}\iff a^{\gcd(m,n)}\equiv b^{\gcd(m,n)}\pmod{d}$$
A: More generally, if $a,b,m,n\in\mathbb Z_{\ge 1}$, $a>b$ and $(a,b)=1$ (as usual, $(a,b)$ denotes $\gcd(a,b)$), then  $$(a^m-b^m,a^n-b^n)=a^{(m,n)}-b^{(m,n)}$$
Proof: Use $\,x^k-y^k=(x-y)(x^{k-1}+x^{k-2}y+\cdots+xy^{k-2}+x^{k-1})\,$   
and use $n\mid a,b\iff n\mid (a,b)$ to prove:    
$a^{(m,n)}-b^{(m,n)}\mid a^m-b^m,\, a^n-b^n\iff$   
$a^{(m,n)}-b^{(m,n)}\mid (a^m-b^m,a^n-b^n)=: d\ \ \ (1)$     
$a^m\equiv b^m,\, a^n\equiv b^n$ mod $d$ by definition of $d$.   
Bezout's lemma gives $\,mx+ny=(m,n)\,$ for some $x,y\in\Bbb Z$.    
$(a,b)=1\iff (a,d)=(b,d)=1$, so $a^{mx},b^{ny}$ mod $d$ exist (notice $x,y$ can be negative).
$a^{mx}\equiv b^{mx}$, $a^{ny}\equiv b^{ny}$ mod $d$.
$a^{(m,n)}\equiv a^{mx}a^{ny}\equiv b^{mx}b^{ny}\equiv b^{(m,n)}\pmod{\! d}\ \ \ (2)$    
$(1)(2)\,\Rightarrow\, a^{(m,n)}-b^{(m,n)}=d$
A: Besides excellent answers above, you can use a property that
$\gcd((y+1)x, y)= \gcd(x,y)$
where $x=a^m - 1, y = a^n - 1$ to find the proof.
A: Apology for adding Answer(Already lot of answers)
It's a beautiful question
In fact, I tried to check on computer.(When I didn't know Bezout's Identity)
I tried to prove as:
Let d = gcd($a^m-1, a^n-1$)
implies: $a^m ≡ 1 $ $mod(d)$ and $a^n ≡  1$ $mod(d)$
Now, $gcd(m,n) = mx+ny$    .........#Bezout's Identity
$a^{gcd(m, n)} ≡ a^{(mx+ny)} ≡  a^{mx}a^{ny} ≡ 1 $ $mod(d)$
Therefore, $ d |a^{gcd(m,n)} −1.$ We now show that $a^{gcd(m,n)} −1 |d.$
Since gcd(m,n) |m, we have
$a^{gcd(m,n)} −1 |a^m −1$     .....#1
Similarly,
$a^{gcd(m,n)} −1 |a^n −1$     .....#2
Since, $a^{gcd(m, n)}-1$ divides both $a^m-1$ and $a^n-1$ so it must also divide their GCD :
$a^{gcd(m, n)}-1| gcd(a^m-1, a^n-1) $ ≡ $mod(d)$
Since, $d |a^{gcd(m,n)}−1$ and $a^{gcd(m,n)}−1 |d$, we must have $d = gcd(a^m−1,a^n−1)$ =
$a^{gcd(m,n)} −1$
So, Bezout's Identity makes the proof simpler.
