The gcd of 2ᵃ − 1 and 2ᵇ − 1

Idea. The Euclidean algorithm on the exponents is mirrored by the Euclidean algorithm on the numbers $2^k-1$.

Key step. For $a>b$,
$$2^a-1=2^{a-b}\bigl(2^b-1\bigr)+\bigl(2^{a-b}-1\bigr),$$
so $\gcd(2^a-1,2^b-1)=\gcd(2^b-1,2^{a-b}-1)$, because $\gcd(u,v)=\gcd(v,u-qv)$ for any integer $q$. Thus the pair of exponents $(a,b)$ is replaced by $(b,a-b)$.

Conclusion. Repeating the subtraction step, the exponents follow the subtractive Euclidean algorithm and end at $(g,g)$ with $g=\gcd(a,b)$ (or at $(g,0)$ if one uses $\gcd(u,0)=u$, where $2^0-1=0$). Hence the gcd equals $2^g-1$.

Divisibility. $2^a-1\mid2^b-1\iff\gcd(2^a-1,2^b-1)=2^a-1\iff2^{\gcd(a,b)}-1=2^a-1\iff\gcd(a,b)=a\iff a\mid b$.

Check. $\gcd(2^{12}-1,2^{18}-1)=\gcd(4095,262143)=63=2^6-1$ ✓.

Lesson. When a gcd involves a parametrised expression, show that the Euclidean algorithm on the parameter reproduces the Euclidean algorithm on the values.