Prove $\gcd (2^n- 1 ;2^m-1) = (2^d-1)$

Question

Looking for a high school level proof of $\gcd (2^n-1 ; 2^m-1)=(2^d-1)$
Where $d= \gcd(m;n)$

Answer 1

$\textbf{Hint:}$Use euclidean algorithm.Denote by $(a,b)$ as the gcd of $a,b$

Observe::$\quad\begin{align}(2^m-1,2^n-1)&=(2^m-1,2^n-1-2^m+1)\\&=(2^m-1,2^m*(2^{n-m}-1))\\&=(2^m-1,2^{(n-m)}-1)\end{align}$ (Assume WLOG $n>m$).

This is similar to, $(m,n)=(m-n,n)$ in the method of finding gcd using the euclidean algorithm.

Answer 2

Assume that $d=(m,n)$ and $p=(2^n-1,2^m-1)$ so that $p | (2^n-1)$ & $p | (2^m-1)$ since $p$ is their GCD. Now since p divides both of them we can write , $$ 2^n \equiv 1 (\text{mod }p )$$ $$ 2^m \equiv 1 (\text{mod }p )$$ Due to Bezout's lemma since $(m,n)=d$ there must exist integers $x,y$ such that $mx+ny=d$ . Using the congruences and raising them to suitable powers and multiplying we conclude , $$ \displaystyle 2^{mx+ny}\equiv 1 (\text{mod }p)$$ This proves that $p | 2^d-1$ which gives $p\le (2^d-1)$ . Now since $d |m$ and $d|n$ we can prove that $2^d-1 | 2^m-1$ and $2^d-1 | 2^n-1$ . But then $(2^d-1)$ is a common divisor of both $(2^m-1)$ and $(2^n-1)$ and it must be less than or equal to the GCD i.e. $2^d-1\le p$ as the GCD is the greatest common divisor.

Thus we conclude that $p=2^d-1$ from the condition $2^d-1\le p \le 2^d-1$ .

Note : If $m|n$ then $2^n-1=2^{mk}-1=(2^m)^k-1=(2^m-1)(...)$ and thus $2^m-1 | 2^n-1$