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?
 A: Let us first determine all the primes $p$ (necessarily odd) which divide both $a$ and $2^a-1$. Writing $a=mp^{\alpha}$, with $\alpha$ maximal, one gets $ 2^{mp^{\alpha}}\equiv 1$ mod $p$, equivalently $2^m\equiv 1$ mod $p$ (by applying repeatedly  F$l$T), equivalently $2^{r_p (m)}\equiv 1$ mod $p$, where $1\le r_p (m)\le p-1$ represents $m$ mod $(p-1)$. Finally, a necessary and sufficient condition is $a=mp^{\alpha}$ and  $r_p (m)$ is a multiple of the order of the class of $2$ in the cyclic group $\mathbf F_p^*$ of order ($p-1$) . 
It remains to determine the maximal power $s$ s.t. $p^s$ divides $a$ and $2^a-1$. In the language of $p$-adic valuations : if $v_p(p^s)=s$, then $s=$ min $(v_p(a),   v_p(2^a-1))$. The precise value of $s$ depends of course on the given $a$. By definition, $v_p(a)=\alpha$. To compute $v_p(2^a-1)$, we can put $a=mq, q=p^{\alpha}$, and use the classical formula $X^q -1 =\prod f_d (X)$, where the product bears on all $d\mid q$ and $f_d(X)$ denotes the $d$-th cyclotomic polynomial of degree $\phi (d)$, $\phi$ being the Euler totient function see e.g. Lang's "Algebra", chap. VIII, §3). By definition, $f_d(X)= \prod (X-\zeta)$, where $\zeta$ runs through all the primitive $d$-th roots of $1$, and we want to compute the $p$-adic valuation of this product for $x=2^m$. Although a direct computation is possible, it is much more convenient to view $x-\zeta$ as an element of the $p$-adic field $K=\mathbf Q_p (\omega)$, where $\omega$ is a fixed primitive $d$-th root of $1$, and use the valuation $v_K$, the extension of $v_p$ to $K$ defined by $v_K(y)=v_p(N(y))/f$, where $f$ is the inertia index of $K/\mathbf Q_p$ and $N$ is the norm . Here,  because $q$ is a power of $p$, $1-\omega$ is a uniformizer and $f=1$ (the ramification index is $e=\phi(d)$). Since the factors $x-\zeta$ are mutual  conjugates, $f_d(x-\zeta)= N(x-\omega)$, so $v_p(f_d(x-\zeta))=v_K(x-\omega)$. But $2^m-\omega=(2^m-1)+ (1-\omega)$, and $v_K(2^m-1)=\phi(d).v_p(2^m-1)\ge \phi(d)>1$ because $d$ is a power of $p$, so $v_p(f_d(\zeta))=v_K(1-\omega)=1$. From this we deduce that  $v_p(2^a-1)=\frac 12(\alpha+1)\alpha$  ./.
