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

$b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1. How can we prove that 
$$
\gcd (b ^ x - 1, b ^ y - 1, b ^ z - 1 ,\dots)= b ^ {\gcd (x, y, z, \dots)} - 1\ ?
$$

Hint $ $ By below $\, a^M\!-\!1,\:a^N\!-\!1\ $ and $\, a^{(M,N)}\!-\!1\ $  have the same set $\,S$ of common divisors $\,d,\, $ so they have the same greatest common divisor $\ (= \max\ S),\,$ i.e. using $\,\rm\color{#90f}{R\! = }$mod order reduction
$$\begin{eqnarray}\ {\rm mod}\:\ d\!:\  a^M\!\equiv 1\equiv a^N&\!\iff\!& {\rm ord}(a)\ |\ M,N\!\color{#c00}\iff\! {\rm ord}(a)\ |\ (M,N)\!\!\!\overset{\rm\color{#90f}R\!\!}\iff\! \color{#0a0}{a^{(M,N)}\!\equiv 1}\\[.3em]
 {\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1\! &\!\iff\!\!&\ d\ |\ \color{#0a0}{a^{(M,N)}\!-\!1},\qquad\,\ {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N)
\end{eqnarray}\ \ \ \ \ $$
Note $ $ We  used the GCD universal property $\ a\mid b,c \color{#c00}\iff a\mid (b,c)\ $ [which is the definition of a gcd in more general rings]. $ $ Compare that with $\ a<b,c \!\iff\! a< \min(b,c),\,$ $a<b,c\,$ and, analogously, $\,  a\subset b,c\iff a\subset b\cap c,\ $ and  $\ a\supset b,c\iff a\supset b\cup c.\,$ Such universal "iff" characterizations enable quick and easy simultaneous proof of both directions.
The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See this answer for more on this and the more familiar additive form of a denominator ideal.
Generally: $\, \gcd(f(m), f(n)) = f(\gcd(m,n))\ $ if $\,  f(n) \equiv f(n\!-\!m)\pmod{\!f(m)}\, $ and $\, f(0) = 0,\,$ which is proved by a simple induction in this answer.
In fact there is a $q$-analog: the result also holds true for polynomials $ \ f(n) = (x^n\!-\!1)/(x\!-\!1),\, $ and $\ x\to 1\ $ yields the integer case (Bezout identity) - see this answer for a simple proof.
