Chapter 4.3, Problem 37E

Show that if a and b are positive integers, then $\left({\text{2}}^a\text{-1}\right)\text{ mod }\left({\text{2}}^b-1\right)={\text{2}}^{a\text{ mod }b}-1$ .

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

[Hint: Show that the remainders obtained when the Euclidean algorithm is used to compute $\text{gcd}\left({\text{2}}^a-1,{\text{2}}^b\text{-1}\right)$ are of the from ${\text{2}}^r\text{-1}$ , where r is a reminder arising when the Euclidean algorithm is used to find $\text{gcd}\left(a,b\right)$ .]