Help me answer this Number Theory question on GCD (involves exponents)

Question

Basically I need a good hint how to solve the problem.I have solved it partly.

$gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$.

I have reached till:

$gcd(2^a-1,2^b-1)=gcd(2^{a-b}-1,2^b-1)$

How to proceed from here.

Please give detailed answer if you are using special manipulation or property please do explain how do you use it in this problem to solve it.

Thanks.

Answer 1

First consider the case when $(a,b)=1$. By Bezout theorem, there exists $u,v>0$ such that $au-bv=1$. Let $\gcd (2^a-1,2^b-1)=t$, then $t|2^{au}-1$, or $2^{bv+1}\equiv 1\pmod t$, or $2\equiv 1 \pmod t$, then $t=1$.

If $\gcd(a,b)=d>1$, then $\gcd \left(\frac{a}{d},\frac{b}{d}\right)=1$ and just apply the above case.

Hint to continue your solution: Just consider Euclide's way to compute the GCD.

Answer 2

We outline a somewhat clumsy induction proof.

Suppose the result holds for all pairs $(a,b)$ with $a\le k$, $b\le k$. We show the result holds for all $(a,b)$ with $a\le k+1$, $b\le k+1$.

So let $a\le k+1$, $b\le k+1$. If $a\le k$ and $b\le k$, we know the result holds. If $a=k+1$ and $b=k+1$, the result is easy to verify. So we can assume that $a=k+1$ and $b\le k$.

By your result, $\gcd(2^a-1,2^b-1)=\gcd(2^{a-b}-1, 2^b-1)$. By the induction assumption, this is $2^{\gcd(a-b,b)}-1$. But $\gcd(a-b,b)=\gcd(a,b)$ so we are finished.

A much nicer conceptual proof is to observe that the process of subtracting the smaller number from the bigger that you initiated is precisely the (original) Euclidean gcd algorithm, so after a number of iterations of your procedure our two numbers are each $2^{\gcd(a,b)}-1$. But that takes a fair bit of notation to write up formally.

Answer 3

Using your lemma, you have the seeds of a variant of Euclid's algorithm.

In particular, wlog, $a>b$ and so $a = db + r$ for some positive $d$ and $0 < r \leq b.$ Therefore, using your lemma $d$ times, shows that $gcd(2^a−1,2^b−1) = gcd(2^b−1, 2^r−1)$ and $gcd(a, b) = gcd(b, r)$ (with this last following from Euclid's algorithm, more or less).

Now, there are two cases, either, r = b, and the RHS is $2^b−1 = 2^{gcd(a, b)} -1$ and we're done, or you need to reduce again, as in Euclid's algorithm. Either way, you eventually find yourself in the first case (after at most b reductions), and then, following the chain of implications back, you'll have your result.