# 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$$

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 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.