Question

Use exercise 36 to show that if a and b are positive integers, then $\gcd \left(2^a-1,2^b-1\right)=2^{\gcd (a,b)}-1$

Short answer

$\gcd \left(2^a-1,2^b-1\right)=2^{\gcd (a,b)}-1$

Step-by-step solution

Step: 1

By exercise 36, we have$\left(2^a-1\right)mod\left(2^b-1\right)=2^{amodb}-1$

$\gcd \left(2^a-1\right)mod\left(2^b-1\right)=\gcd \left(2^{amodb}-1\right)$

Because the exponent involved in the calculation are b and a mod b, the same as the quantities involved in computing $\gcd (a,b)$, the steps used by the Euclidean algorithm to compute $\gcd (a,b)$and show that$\gcd \left(2^a-1,2^b-1\right)=2^{\gcd (a,b)}-1$