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

• Another question (math.stackexchange.com/questions/11567/…) was closed as a duplicate of this one where there is a second solution. Commented Dec 4, 2010 at 14:17
• Find here: Number Theory for Mathematical Contests, Example#245, Page#36. Commented Jul 29, 2012 at 16:56
• And what if we consider GCD over $\mathbb{C} [X]$? Commented Dec 10, 2019 at 6:11
• @labbhattacharjee hey i know it's been 8 years but I just stumbled upon this post and I found that link quite interesting. Do you have more of that kind of material (mathematical contests)? Commented Nov 3, 2020 at 4:04
• @NotAMathematician, See pdfdrive.com/… and fmf.uni-lj.si/~lavric Commented Nov 5, 2020 at 5:07

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 above and in the Euclidean algorithm $$\rm\: (A,m) = (A\bmod m,\,m),\,$$ i.e. 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 by 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}\\[.3em] {\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,\,$$ hence 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 - just like above.

The conceptual structure at the core 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.

• Sort of like the Fibonacci sequence! Commented May 23, 2015 at 12:03
• @john Yes, they are both strong divisibility sequences, i.e. $\,(f_n,f_m) = f_{(n,m)}.\,$ See here for the Fibonacci case. Commented May 23, 2015 at 13:33

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 \\[.1em] \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 \\[.1em] & &=&\rm ((m,n)') \quad\ \:\! by\ \ r \equiv n\ \:(mod\ m)\quad\ \ \bf\small 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
Commented Jun 18, 2012 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).$ Commented Jun 19, 2012 at 0:17

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

• I don't understand why you can conclude that $(a^{\gcd(n,m)}-1)\mid t$ from $a^{\gcd(n,m)}\equiv 1\pmod t$. The latter will give you $t\mid (a^{\gcd(n,m)}-1)\$.
– Bach
Commented Dec 27, 2020 at 20:28
• How did you manage to conclude, which would require that $k=1$: $$a^{\gcd(m,n)}-1\, =\gcd(a^m-1, a^n-1)$$ Commented May 31, 2021 at 4:25
• To prove $(a^{\gcd(n,m)}-1)\big|t$, I would try to show that $(a^{\gcd(n,m)}-1)$ divides both $(a^{m}-1)$ and $(a^{n}-1)$. As it is a common divisor, it must divide their greatest common divisor, $t$. Commented Oct 3, 2021 at 17:42

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. Commented Dec 31, 2016 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! Commented Dec 31, 2016 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. Commented Jul 13, 2017 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}$? Commented Dec 2, 2018 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$

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. Commented Oct 2, 2019 at 9:26
• That was a typo. Thanks for noticing it. Does it make more sense now?
– robjohn
Commented Oct 2, 2019 at 14:07
• Why you are using "if....". What if, "if..." doesn't hold true Commented Oct 2, 2019 at 14:14
• It does in the case of $y=1$ due to the preceding line. The subsequent lines finish the induction.
– robjohn
Commented Oct 2, 2019 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. Commented Oct 2, 2019 at 14:21

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.

I thought I'd contribute a rather nonstandard answer using ideas from category theory. I wouldn't say that any undergraduate number theory student should be expected to follow this reasoning nor am I claiming this is a particularly great approach to number theory! It's merely a bit of fun for those who like this kind of thing.

We consider $$\mathbb{N}$$ as a poset where $$a\leq b\iff a|b$$ and thus a category. Posetal categories are particularly pleasant types of categories as all squares, triangles etc. commute automatically. This will mean in a number of places we have little to check (whereas usually we'd have to check various "naturality" conditions).

Step 1:

The product $$A\times B$$ of two objects $$A,B$$ in a category, if it exists, is characterised by:

• it coming with two projection morphisms $$\pi_1:A\times B \to A,\pi_2:A\times B\to B$$
• given maps $$f:C\to A,g:C\to B$$ we get a unique map $$\langle f,g\rangle :C\to A\times B$$ such that $$\pi_1\circ\langle f,g\rangle = f, \pi_2\circ\langle f,g\rangle = g$$.

Here the objects in question are natural numbers $$m,n$$ and if $$k$$ is their categorical product (supposing it exists) then:

• the first bullet point just tells us that $$k|m$$ and $$k|n$$
• the second bullet point says that if $$l|m,l|n$$ then $$l|k$$

In other words, $$k$$ is precisely $$\text{gcd}(m,n)$$ and always exists.

Step 2:

We now claim that the mapping $$n \mapsto a^n-1$$ is in fact a functor $$\mathbb{N}\to \mathbb{N}$$. Clearly it gives an assignment of objects of $$\mathbb{N}$$ to other objects of that category but to be a functor it must also send morphisms to morphisms, i.e. if $$m|n$$ then it must be the case $$a^m-1|a^n-1$$. But this is clearly the case just by thinking about the abstract polynomials $$x^m-1| x^n-1$$ dividing each other as $$x^n-1 = (x^m-1)(x^{n-m} + x^{n-2m} + \ldots + 1)$$ The rest of the conditions of a functor (normally called "functoriality") immediately follow due to the fact that all diagrams commute in $$\mathbb{N}$$.

Step 3:

Now the statement of the theorem $$\text{gcd}(a^n-1,a^m-1) = a^{\text{gcd}(n,m)}-1$$ then just says that the functor $$a^{(-)}-1$$ preserves products. To prove this, we could of course just immediately do some number theory (which will eventually be necessary). However a natural categorical approach here would be to check if it has a left adjoint as all functors with left adjoints preserve all small limits and binary categorical products are one of the simplest examples of a nontrivial limit.

A left adjoint would be a functor $$F:\mathbb{N}\to \mathbb{N}$$ such that for all pairs of integers $$m,n$$ we have $$F(m)|n \iff m| a^n-1$$ The naturality condition normally part of an adjunction will automatically follow once such an $$F$$ is followed as, again, all diagrams commute in this category $$\mathbb{N}$$.

Well $$m|a^n-1$$ is equivalent to saying that $$a^n \equiv 1 \pmod{m}$$ which is itself (rather obviously) equivalent to the statement that $$n$$ is a multiple of the multiplicative order of $$a$$ modulo $$m$$, which we'll write as $$\text{ord}_m(a)$$. (We also learn that $$a$$ must be coprime to $$m$$ for this situation to ever arise but that's not important here.)

We will thus be done if the assignment $$m\mapsto \text{ord}_m(a)$$ is functorial because then we can take this to be $$F$$. In particular, we require that if $$m|n$$ then $$\text{ord}_a(m)|\text{ord}_a(n)$$.

But note that $$a^{\text{ord}_a(n)}\equiv 1\pmod{n}\implies a^{\text{ord}_a(n)}\equiv 1\pmod{m}$$ since $$m|n$$. Thus we must have $$\text{ord}_a(m)|\text{ord}_a(n)$$ and we are done.

Perhaps this was fun to a certain audience; it definitely makes me smile. I think that in fact there are a lot of adjoints hiding away in various elementary number theory statements (even in the proofs of Bill Dubuque across MSE) and perhaps at some point I'll have to make a mini-survey of such ideas.

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.

It is enough to check that if $$(m,n) = 1$$ then the resultant

$$R_{m,n} \colon =\operatorname{res}(\frac{x^m-1}{x-1}, \frac{x^n-1}{x-1}) = 1$$

Now we have

$$R_{m,n} = \prod_{\xi^n=1, \xi \ne 1} \frac{\xi^m-1}{\xi-1}$$

Now, since $$(m,n) = 1$$, the map $$\xi \mapsto \xi^m$$ is a bijection of $$\{\xi^n=1, \xi \ne 1\}$$. We conclude that $$R_{m,n} = 1$$.