number theory - What is $operatorname{gcd}(a,2^a-1)$?

Intuitively, I feel it's $1$, for example $(2, 3), (3,7)$ etc. But then I cannot go to prove it. Using the formula $ax+by=c$ does not make sense because of the power.
Is it possible by induction? If I assume $a=1$, then $\operatorname{gcd}(1, 2^1-1)=1$ Assuming, it to be true for $k$, then

$$\operatorname{gcd}(k,2^k-1)=1 = kx+(2^k-1)y=1$$

I'm stuck here. Is it even possible with this method?