Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
4  
Please tag as "homework" if this is one. Otherwise, here's your hint: $(a^n-1)=(a-1)(1+a+a^2+\dots)$ –  J. M. Oct 22 '10 at 0:48
1  
Another question (math.stackexchange.com/questions/11567/…) was closed as a duplicate of this one where there is a second solution. –  Qiaochu Yuan Dec 4 '10 at 14:17

4 Answers 4

Note $\rm\ f_{\,n}\: :=\ a^n\!-\!1\ =\ a^{n-m} \: (a^m\!-\!1) + a^{n-m}\!-\!1,\:$ i.e. $\rm\ \color{#C00}{f_{\,n}\! = f_{\,n-m}\! + k\ f_{\,m}},\ k\in\mathbb Z.\:$ Now apply

Theorem $\: $ Let $\rm\ f_{\, n}\: $ be an integer sequence with $\rm\ f_{\,0} =\, 0\: $ and $\rm \:\color{#C00}{ f_{\,n}\!\equiv f_{\,n-m}\ (mod\ 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.

share|improve this answer

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,\:$ which allows us to view the result 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.

share|improve this answer
    
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

Find here: Number Theory for Mathematical Contests, Example#245, Page#36.

share|improve this answer
    
This is an awesome resource! Do you have more like this? –  BeetleTheNeato Apr 23 '13 at 18:45
    

Let

$gcd(m,n)=k$ then

$(a^m-1)=(a^{xk}-1)$ and $(a^n-1)=(a^{yk}-1)$

take $a^k=b$ then using

$(b^n−1)=(b−1)(1+b+b^2+…)$ get the answer

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.