Tenga en cuenta que tanto $2^a+1$ $2^b+1$ son impares, por lo que cualquier divisor común es impar.
Ahora, si $d$ divide $2^a+1$$2^b+1$, entonces también se divide $(2^a+1)-(2^b+1) = 2^a-2^b$, por lo tanto se divide $2^{\min(a,b)}(2^{|a-b|}- 1)$. Pero desde $d$ es impar, entonces $d$ divide $2^{|a-b|}-1$. Es decir, si, por ejemplo, $a\geq b$, luego
$$d|2^{a}-1,2^b-1 \Longleftrightarrow d|2^a-1, 2^b-1, 2^{a-b}-1.$$
Pero si $d$ divide tanto a a$2^{a-b}-1$$2^b-1$, a continuación, divide
$$2^b(2^{a-b}-1) + (2^b-1) = 2^a-1.$$
Así:
$$d|2^a-1,2^b-1 \Longleftrightarrow d|2^b-1, 2^{a-b}-1.$$
Estamos asumiendo $a\geq b$; tenga cuidado con esa suposición; de forma más general, tenemos:
$$\text{For }a,b\text{ odd, }\gcd(2^a-1,2^b-1) = \gcd(2^{\min(a,b)}-1, 2^{|a-b|}-1).$$
Esto se parece mucho a la dpc de identidad
$$\gcd(x,y) = \gcd(y,x-y),$$
lo cual es muy útil. Tal vez usted puede hacer el trabajo para usted?