I am trying to prove the following:
$$(2^a - 1, 2^b - 1) = 2^{(a,b)} - 1 \ \ \ \forall a,b \in \mathbb{N} $$ Where: $$ (a,b) := \gcd(a,b) $$
So far I have tried dividing $2^a-1$ by $2^b-1$ to see if there was anyway to get the remainder, and user the remainder to help inductively show what the $gcd$ tends toward, but all I could do through algebraic manipulation was a pathetic:
$$ \frac{2^a-1}{2^b-1} = \frac{2^a}{2^b-1} - \frac{1}{2^b-1}$$
Which wasn't in the form that I wanted. I needed a remainder.
I also, tried find a recurrence relation, which ends up being:
$$ a_1 = 1, a_n = 2a_{n-1} + 1$$
But, after that, I couldn't really think of anything I could do with it. (Don't even know why I bothered doing this in the first place...)
Then I started thinking in terms of induction:
Maybe let $a$ be an arbitrary natural number, and show that $$(2^a-1, 2^1-1) = (2^a-1,1) = 1 = 2^1 - 1 = 2^{(a,1)} - 1$$
But after the base case I was stumped:
Assume it holds true for all $k$ then if it holds for $k+1$ our claim is true:
$$ (2^a - 1, 2^{k+1} - 1) = (2^a - 1, 2 \cdot 2^k - 1) = ???$$
I don't even think you can use induction quite this way, I've just trying to come up with something. Anyone have any hints? Thank you.
Somewhat in line with the division idea, you can use the property that $(a,b)=(a-b,b)$ (this is the basis for Euclid's algorithm). In your case, assuming $a>b$, \begin{align*} (2^a-1, 2^b-1) &= ((2^a-1) - 2^{a-b}(2^b-1), 2^b-1)\\ &= (2^{a-b} - 1, 2^b - 1). \end{align*} Notice that the exponents have a property analogous to the GCD one. Just to be clear, if we define $f(a,b) = (2^a-1,2^b-1)$, we can write $f(a,b)=f(a-b,b)$.
This means that if we follow all of the steps to compute the GCD of $a$ and $b$ by Euclid's algorithm, we can carry the steps over to get that $f(a,b)=2^{(a,b)}-1$.