Prove that $gcd \left(2^{x}-1, 2^{y}-1\right) = 2^{gcd(x,y)}-1$

Question

My attempt:

1) Try to use normal definition of gcd:

$(a,b)=d\Rightarrow as_1+bs_2=d$ for some $s_1,s_2\in \mathbb Z \tag1$

So $\left(2^{x}-1, 2^{y}-1\right)=s_1(2^x-1)+s_2(2^y-1),\quad s_i\in\mathbb Z$

and similarly $2^{(x,y)}-1=2^{t_1x+t_2y}-1, \quad t_i\in\mathbb Z\tag 2$

Solving $(1),(2)$ together, we have:

$2^{t_1x+t_2y}-s_12^x-s_22^y+s_2-s_1-1=0$

I tried to make quadratic equation $(2^{t_1x}-A)(2^{t_2y}-B)$ for some suitable A,B but failed.

2) I tried to use binomial expansion $(a+b)^n=\sum\binom{n}{k}a^kb^{n-k}$ and $a^n-1=(a-1)(a^{n-1}+...+1)$ but failed again.

There must be elegant solution I guess.

Answer 1

Suppose that $x<y$. Then $$(2^y-1)-2^{y-x}(2^x-1)=2^{y-x}-1.$$ Therefore $$\gcd(2^x-1,2^y-1)=\gcd(2^x-1,2^{y-x}-1).$$ Now we can use induction on $\max(x,y)$.

This argument also works for other values of $2$.

Answer 2

$$ x < y, gcd(2^{x}-1, 2^{y}-1) = gcd(2^{x}-1, 2^{y}-2^{x}) = gcd(2^{x}-1, 2^{y}-2^{x}-1), gcd(2^{x}, 2^{x}-1) = 1 \Rightarrow gcd(2^{x}-1, 2^{y}-1) = gcd(2^{x}-1, 2^{y-x}-1) $$ Hence Euclid's algorithm for the exponents is fulfilled.