Let $a$ and $b$ be nonnegative integers. prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$

Question

Let $a$ and $b$ be nonnegative integers. prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1.$

So far I have tried using Linear Diophantine Equations, the GCD With Remainder theorem (replacing one input into the gcd with the remainder of the bigger term divided by the smaller term), and writing $d=gcd(a,b)$, let $a=ds, b=dr$, but I am still stuck.

Thanks.

Answer 1

Let $d = gcd(a, b), a > b, (x, y) := gcd(x, y)$. $$(2^a-1, 2^b-1) = (2^{a}(2^{b-a}-1), 2^a-1) = (2^{b-a}-1, 2^a-1) = \ldots = 2^d - 1 $$ Compare the above with the derivation of d = gcd(x, y).

For time reason I cannot write it in detail. I am sorry and I will edit this post latter.