# Powers of a greatest common denominator [duplicate]

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

-

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

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