AMC 12 Mock Exam 3 Problem 9

Problem 9 of 25

What is the greatest common divisor of $2^{30}-1$ and $2^{42}-1$ ?

Show solution

Solution

For $a>b$ , $2^a-1=2^{a-b}(2^b-1)+(2^{a-b}-1)$ , so $\gcd(2^a-1,2^b-1)=\gcd(2^b-1,2^{a-b}-1)$ : the exponents follow the Euclidean algorithm. Since $\gcd(42,30)=\gcd(30,12)=\gcd(12,6)=6$ , the answer is $2^6-1=\boxed{63}$ .

Tagged: gcd of numbers of the form $2^m-1$

Answer choices

Solution