Jtdylktuy

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

$rmdisplaystylequadquadquadquadquadquadquad 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 $rmdisplaystyle quad n' : := frac{x^n - 1}{x-1}:$. $quad$ Note $rmquad n' = n $ for $rm x = 1$.

Theorem $rmquad (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 \
quadRightarrowquad &rmqquad n' &=& rm x^r m' + r' quad rm by dividing above by x!-!1 \
quadRightarrow &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.

Let $mge nge 1$. Apply Euclidean Algorithm.

$gcdleft(a^m-1,a^n-1right)=gcdleft(a^{n}left(a^{m-n}-1right),a^n-1right)$. Since $gcd(a^n,a^n-1)=1$, we get

$gcdleft(a^{m-n}-1,a^n-1right)$. Iterate this until it becomes $$gcdleft(a^{gcd(m,n)}-1,a^{gcd(m,n)}-1right)=a^{gcd(m,n)}-1$$

More generally, if $gcd(a,b)=1$, $a,b,m,ninmathbb 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.

$$dmid a^m-b^m, a^n-b^niff left(ab^{-1}right)^mequiv left(ab^{-1}right)^nequiv 1pmod{d}$$

$$iff text{ord}_{d}left(ab^{-1}right)mid m,niff text{ord}_{d}left(ab^{-1}right)mid gcd(m,n)$$

$$iff left(ab^{-1}right)^{gcd(m,n)}equiv 1pmod{d}iff a^{gcd(m,n)}equiv b^{gcd(m,n)}pmod{d}$$

More generally, if $a,b,m,ninmathbb 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 $nmid a,biff nmid (a,b)$ to prove:

$a^{(m,n)}-b^{(m,n)}mid a^m-b^m,, a^n-b^niff$

$a^{(m,n)}-b^{(m,n)}mid (a^m-b^m,a^n-b^n)=: d (1)$

$a^mequiv b^m,, a^nequiv b^n$ mod $d$ by definition of $d$.

Bezout's lemma gives $,mx+ny=(m,n),$ for some $x,yinBbb Z$.

$(a,b)=1iff (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$

Let
$$gcd(a^n - 1, a^m - 1) = t$$
then
$$a^n equiv 1 ,big(text{ mod } tbig),quadtext{and}quad,a^m equiv 1 ,big(text{ mod } tbig)$$
And thus
$$a^{nx + my} equiv 1, big(text{ mod } tbig)$$
$forall,x,,yin 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 } tbig) = a^{gcd(n,m)} equiv 1 big(text{ mod } tbig)impliesbig( a^{gcd(n,m)} - 1big) 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-1right)$, then
$$
left(p^g-1right)sum_{k=0}^{frac ag-1}p^{kg}=p^a-1
$$
and
$$
left(p^g-1right)sum_{k=0}^{frac bg-1}p^{kg}=p^b-1
$$
Thus, we have that
$$
left.p^g-1,middle|,Gright.
$$

For $xge0$,
$$
left(p^a-1right)sum_{k=0}^{x-1}p^{ak}=p^{ax}-1
$$
Therefore, we have that
$$
left.G,middle|,p^{ax}-1right.
$$
If $left.G,middle|,p^{ax-(b-1)y}-1right.$, then
$$
left(p^{ax-(b-1)y}-1right)-p^{ax-by}left(p^b-1right)=p^{ax-by}-1
$$
Therefore, for any $x,yge0$ so that $ax-byge0$,
$$
left.G,middle|,p^{ax-by}-1right.
$$
which means that
$$
left.G,middle|,p^g-1right.
$$

Putting all this together gives
$$
G=p^g-1
$$