GCD of large numbers

Theorem:

$\gcd(2^a-1, 2^b-1)=2^{\gcd(a,b)}-1$ for some integers $a$ , $b$ .

Proof:

Let $d=\gcd(2^a-1, 2^b-1)$ .

We have that $\gcd(a,b)$ is always $ax+by$ for some integers $x,y$ .

We want to prove that $d=2^{\gcd(a,b)}-1$ . It would be sufficient to prove that $d\mid 2^{\gcd(a,b)}-1$ and $2^{\gcd(a,b)}-1\mid d$ .

$1)$ We know that $2^a\equiv 1\pmod d$ and $2^b\equiv 1\pmod d$ , therefore $2^{\gcd(a,b)}\equiv (2^a)^x (2^b)^y\equiv 1\pmod d$ . Hence $d\mid 2^{\gcd(a,b)}-1$ .

$2)$ We have $2^{\gcd(a,b)}-1\mid (2^{\gcd(a,b)})^k-1^k=2^a-1$ for some integer $k$ . Similarly $2^{\gcd(a,b)}-1\mid 2^b-1$ . Hence $2^{\gcd(a,b)}-1\mid d$ .

$(1)(2)\iff d=2^{\gcd(a,b)}-1$ .