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

Answer

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.

Attribution
Source : Link , Question Author : Community , Answer Author : Bill Dubuque

Leave a Comment