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:
Number theory proving question?

Dear friends,

Since $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 ,\ldots)= b ^ {\gcd (x, y, z, .. .)} - 1 $$ ?

Thank you!

Paulo Argolo

share|improve this question

marked as duplicate by Qiaochu Yuan, Aryabhata, Robin Chapman, KennyTM Nov 25 '10 at 20:07

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.

    
This is essentially a duplicate of this previous question coupled with induction math.stackexchange.com/questions/7473/… –  Timothy Wagner Nov 23 '10 at 20:09
1  
@Timothy: ah, you're right. I should've checked for duplicates. –  Qiaochu Yuan Nov 23 '10 at 20:20

2 Answers 2

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 & 1 \pmod{a^{\gcd(n,m)}-1} \\ a^m-1 = (a^{\gcd(n,m)})^f-1 \equiv & 1 \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$.

share|improve this answer

Hint $\ $ By below $\,\ a^M\!-\!1,\:a^N\!-\!1\ $ and $\,\ a^{\,(M,N)}\!-\!1\ $ have the same set $\,S\,$ of common divisors $\,d,\, $ therefore they have the same greatest common divisor $\ (= \max\ S).$

$$\begin{eqnarray}\ \ {\rm mod}\,\ d\!:\ \ a^M,\:a^N\equiv 1&\!\iff\!\!& {\rm ord}(a)\ |\ M,N\color{#c0d}\iff {\rm ord}(a)\ |\ (M,N)\iff \color{#c00}{a^{\,(M,N)}\equiv 1}\\ {\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1 &\!\iff\!\!&\ d\ |\ \color{#c00}{a^{\,(M,N)}\!-\!1},\qquad\ \ \, {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N) \end{eqnarray}$$

Remark $ $ Above we used $\ a\mid b,c \color{#c0d}\iff a\mid (b,c),\, $ the fundamental universal property of the gcd. Compare $\ a<b,c \!\iff\! a< \min(b,c),\ $ and $\,\ a\subset b,c\iff a\subset b\cap c.\ $ Such universal "iff" characterizations enable quick and easy simultaneous proof of both directions of the equivalence.

The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See my post here 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)\ \ ({\rm mod}\ f(m))\ $ and $\ f(0) = 0.\, $ See my post here for a simple inductive proof.

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 my post here for a simple proof.

share|improve this answer

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