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

$\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 sequence with $\rm\ f_{0} =\, 0,\:$ $\rm \:{ f_{\,n}\!\equiv \color{#0a0}{f_{\,n-m}}\ (mod\ \color{#c00}{f_{\,m})}}\$ for $\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 = 0\$ or $\rm\: m = 0.\:$
So we may assume $\rm\:n > m > 0\:$.$\$ Note $\rm\ (f_{\,n},f_{\,m}) = (f_{\,n-m},f_{\,m})\$ follows from the hypothesis.
Since $\rm\ (n-m)+m \ <\ n+m,\$ induction yields $\rm \ (f_{\,n-m},f_{\,m})\, =\, f_{\,(n-m,\:m)} =\, f_{\,(n,\:m)}.$

See also this post for a conceptual proof exploiting the innate structure - an order ideal.

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)')\$ 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.

• Is $((\rm m,n)')$ supposed to be $((\rm m,n))'$ i.e. $\rm \dfrac{x^{(m,n)}-1}{x-1}$? – Pedro Tamaroff Jun 18 '12 at 23:38
• @Peter  Let $\rm\:(m,n)' = \dfrac{x^{\,(m,n)}\!-\!1}{x\!-\!1} =: f.\:$ Then $\rm\:((m,n)') = (f) = f\:\mathbb Z[x]\:$ is a principal ideal, thus the equality $\rm\:(m',n') = ((m,n)')\:$ denotes the ideal equality $\rm\:(g,h) = (f)\:$ for polynomials $\rm\:f,g,h\in\mathbb Z[x].\:$ If you have no knowledge of ideals you can instead simply interpret it as saying that $\rm\:f\:|\:g,h\:$ and $\rm\:f = a\,g+b\,h\:$ for some $\rm\:a,b\in \mathbb Z[x],\:$ which implies $\rm\:f = gcd(g,h).$ – Bill Dubuque Jun 19 '12 at 0:17

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

• And this too is a duplicate of an answer in the 5-year-old linked duplicate thread. – Bill Dubuque Dec 31 '16 at 2:07

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

• This is precisely the homogenization $(a^n-1\to a^n-b^n)$ of a proof in the 5-year-old duplicate thread linked in Yuan's comment on the question. To avoid posting such duplicate answers it's a good ides to first peruse duplicate links before posting an answer to a five year old question! – Bill Dubuque Dec 31 '16 at 2:03
• Update: actually this homegenized version was posted 5 months prior in this answer.. There are probably older dupes too since this is a FAQ. Posting the link in case anyone decides to organize. – Bill Dubuque Jul 13 '17 at 20:44
• I didn't understand why if gcd$(a,b) =1$ then gcd$(b, d) =1$? and why $\left(ab^{-1}\right)^m\equiv \left(ab^{-1}\right)^n\equiv 1\pmod{d}$? – Vmimi Dec 2 '18 at 23:48

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$

• What is $d$? I don't understand why gcd$(b, d)=1$ and why do you need that to be true? – Vmimi Nov 30 '18 at 0:22

Let $$\gcd(a^n - 1, a^m - 1) = t$$ then $$a^n \equiv 1 \,\big(\text{ mod } t\big),\quad\text{and}\quad\,a^m \equiv 1 \,\big(\text{ mod } t\big)$$ And thus $$a^{nx + my} \equiv 1\, \big(\text{ mod } t\big)$$ $\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 \,\big(\text{ mod } t\big) = a^{\gcd(n,m)} \equiv 1 \big(\text{ mod } t\big)\implies\big( a^{\gcd(n,m)} - 1\big) \big| t$$

Therefore $$a^{\gcd(m,n)}-1\, =\gcd(a^m-1, a^n-1)$$

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

• Can you elaborate on the step $if G \mid p^{ax-(b-1)y}$. How you arrived on this term. – nature1729 Oct 2 at 9:26
• That was a typo. Thanks for noticing it. Does it make more sense now? – robjohn Oct 2 at 14:07
• Why you are using "if....". What if, "if..." doesn't hold true – nature1729 Oct 2 at 14:14
• It does in the case of $y=1$ due to the preceding line. The subsequent lines finish the induction. – robjohn Oct 2 at 14:18
• I feel you should mention the induction argument more clearly. After you edited solution, it appears inductive in nature. Still some more clarity will be helpful. – nature1729 Oct 2 at 14:21