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

It suffices to prove it for two terms, that is, $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n,m)} - 1$.  The basic idea is that we can use the Euclidean algorithm on the exponents, as follows: if $n > m$, then
$$\gcd(a^n - 1, a^m - 1) = \gcd(a^n - 1, a^n - a^{n-m}) = \gcd(a^{n-m} - 1, a^m - 1).$$
So we can keep subtracting one exponent from the other until we get $\gcd(n, m)$ as desired.  Another way to look at this computation is to write $d = \gcd(a^n - 1, a^m - 1)$ and note that
$$a^n \equiv 1 \bmod d, a^m \equiv 1 \bmod d \Rightarrow a^{nx+my} \equiv 1 \bmod d$$
from which it readily follows, as before, that $a^{\gcd(n,m)} \equiv 1 \bmod d$, so $d$ dividess $a^{\gcd(n,m)} - 1$.  On the other hand, $a^{\gcd(n, m)} - 1$ also divides $d$. To see this, denote $e \cdot \gcd(n,m) = n$ and $f \cdot \gcd(n,m) = m$ (verify for yourrself that this makes sense). We then have 
\begin{align*}a^n-1 = (a^{\gcd(n,m)})^e -1 \equiv & 0 \pmod{a^{\gcd(n,m)}-1} \\
a^m-1 = (a^{\gcd(n,m)})^f-1 \equiv & 0 \pmod{a^{\gcd(n,m)}-1}.
\end{align*} 
Hence we have $$a^{\gcd(n,m)}-1 \; |\; d .$$
What's really nice about this result is that it holds both for particular values of $a$ and also for $a$ as a variable, e.g. in a polynomial ring with indeterminate $a$.  
You can readily deduce several seemingly nontrivial results from this; for example, the sequence defined by $a_0 = 2, a_n = 2^{a_{n-1}} - 1$ is a sequence of pairwise relatively prime integers, from which it follows that there are infinitely many primes.  By working only slightly harder you can deduce that in fact there are infinitely many primes congruent to $1 \bmod p$ for any prime $p$.
