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.

Possible Duplicate:
Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

Given $n \ge 1$ and $s, t \in \mathbb{Z}^{+}$, $s \ge t$, prove that $$\gcd(n^{s} - 1, n^{t} - 1) = n^{\gcd(s, t)} - 1$$

I've been looking at this problem for a while now, but I'm not certain where to begin. Can induction on $s$ be used to prove the result for $n \geq 1$ since $s \ge t$?

share|improve this question

marked as duplicate by Gerry Myerson, Ross Millikan, David Moews, Mike Spivey, 5PM Jan 23 '13 at 4:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
What remainder do you get when you divide $n^s-1$ by $n^t-1$? Show that if $a=bq+r$ then $\gcd(a,b)=\gcd(b,r)$, apply it to this situation, and compare to the Euclidean algorithm for finding $\gcd(s,t)$. –  Gerry Myerson Jan 23 '13 at 3:17
    
    
And a bit more generally, math.stackexchange.com/questions/262130/…? –  Gerry Myerson Jan 23 '13 at 3:29

1 Answer 1

up vote 1 down vote accepted

Hint $\rm\,\ mod\ any\ d\!:\ \ n^s,n^t\equiv 1\iff ord(n)\ |\ s,t\iff ord(n)\ |\ (s,t)\iff n^{(s,t)}\equiv 1 $

Therefore $\rm\ d\ |\ n^s\!-\!1,\:n^t\!-\!1 \iff d\ |\ n^{(s,t)}\!-\!1.\ $ Therefore $\,\rm \{n^s\!-\!1,\:n^t\!-\!1\}\,$ and $\rm\, n^{(s,t)}\!-1\,$ have the same set D of common divisors, hence they have the same greatest common divisor (= max D).

share|improve this answer
    
Did you notice that your friend Bill had already posted an answer to the question I flagged as a duplicate? –  Gerry Myerson Jan 23 '13 at 3:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.