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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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,…? – Gerry Myerson Jan 23 '13 at 3:29
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|cite|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.