For all $a, m, n \in \mathbb{Z}^+$,

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


11 Answers 11


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

  • $\begingroup$ Sort of like the Fibonacci sequence! $\endgroup$
    – cactus314
    Commented May 23, 2015 at 12:03
  • 2
    $\begingroup$ @john Yes, they are both strong divisibility sequences, i.e. $\,(f_n,f_m) = f_{(n,m)}.\,$ See here for the Fibonacci case. $\endgroup$ 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.

  • $\begingroup$ Is $((\rm m,n)')$ supposed to be $((\rm m,n))'$ i.e. $\rm \dfrac{x^{(m,n)}-1}{x-1}$? $\endgroup$
    – Pedro
    Commented Jun 18, 2012 at 23:38
  • $\begingroup$ @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).$ $\endgroup$ 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$.

  • 1
    $\begingroup$ 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)\ $. $\endgroup$
    – Bach
    Commented Dec 27, 2020 at 20:28
  • $\begingroup$ How did you manage to conclude, which would require that $k=1$: $$a^{\gcd(m,n)}-1\, =\gcd(a^m-1, a^n-1) $$ $\endgroup$ Commented May 31, 2021 at 4:25
  • 2
    $\begingroup$ 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$. $\endgroup$
    – kctong529
    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$$

  • 1
    $\begingroup$ And this too is a duplicate of an answer in the 5-year-old linked duplicate thread. $\endgroup$ 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}$$

  • $\begingroup$ 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! $\endgroup$ Commented Dec 31, 2016 at 2:03
  • $\begingroup$ 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. $\endgroup$ Commented Jul 13, 2017 at 20:44
  • $\begingroup$ 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}$? $\endgroup$
    – Vmimi
    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 $$

  • $\begingroup$ Can you elaborate on the step $if G \mid p^{ax-(b-1)y}$. How you arrived on this term. $\endgroup$
    – nature1729
    Commented Oct 2, 2019 at 9:26
  • $\begingroup$ That was a typo. Thanks for noticing it. Does it make more sense now? $\endgroup$
    – robjohn
    Commented Oct 2, 2019 at 14:07
  • $\begingroup$ Why you are using "if....". What if, "if..." doesn't hold true $\endgroup$
    – nature1729
    Commented Oct 2, 2019 at 14:14
  • $\begingroup$ It does in the case of $y=1$ due to the preceding line. The subsequent lines finish the induction. $\endgroup$
    – robjohn
    Commented Oct 2, 2019 at 14:18
  • $\begingroup$ 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. $\endgroup$
    – nature1729
    Commented Oct 2, 2019 at 14:21

Apology for adding Answer(Already lot of answers)

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


You must log in to answer this question.