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

0
2019-05-18 23:54:55
Source Share

Below is an evidence which has the cool attribute that it quickly specializes to an evidence of the integer Bezout identification for $\rm\:x = 1,\:$ permitting us to watch it as a q-analog of the integer instance.

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

Theory $\rm\quad (m',n')\ =\ ((m,n)')\$ for naturals $\rm\:m,n.$

Proof $\$ It is trivially real if $\rm\ m = n\$ or if $\rm\ m = 0\$ or $\rm\ n = 0.\:$

W.l.o.g. intend $\rm\:n > m > 0.\:$ We continue 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\$ over, i.e. get rid of tops.

A much deeper understanding comes when one researches Divisibility Sequences and also Divisor Theory.

0
2019-05-21 10:19:21
Source

$\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.\:$ Apply

Theorem $\:$ If $\rm\ f_{\, n}\:$ is an integer series with $\rm\ f_{0} =\, 0,\:$ $\rm \:{ f_{\,n}\!\equiv \color{#0a0}{f_{\,n-m}}\ (mod\ \color{#c00}{f_{\,m})}}\$ for $\rm\: n > m,\$ after that $\rm\: (f_{\,n},f_{\,m})\ =\ f_{\,(n,\:m)} \:$ where $\rm\ (i,\:j)\$ represents $\rm\ gcd(i,\:j).\:$

Proof $\$ By induction on $\rm\:n + m\:$. The theory is trivially real if $\rm\ n = m\$ or $\rm\ n = 0\$ or $\rm\: m = 0.\:$
So we might think $\rm\:n > m > 0\:$. $\$ Note $\rm\ (f_{\,n},f_{\,m}) = (f_{\,n-m},f_{\,m})\$ adheres to from the hypothesis.
Given that $\rm\ (n-m)+m \ <\ n+m,\$ induction returns $\rm \ (f_{\,n-m},f_{\,m})\, =\, f_{\,(n-m,\:m)} =\, f_{\,(n,\:m)}.$

See additionally this post for a theoretical evidence manipulating the natural framework - an order perfect .

0
2019-05-19 23:37:53
Source