Prove that gcd(2^m - 1, 2^n - 1) = 2^{gcd(m, n)} - 1, and use it to compute gcd(2^{100} - 1, 2^{60} - 1).

Prove that gcd(2^m - 1, 2^n - 1) = 2^{gcd(m, n)} - 1, and use it to compute gcd(2^{100} - 1, 2^{60} - 1).

Approach: Show that reducing the exponents mirrors one step of the Euclidean algorithm, using the factorisation of 2^m - 1 as 2^{m-n}(2^n - 1) plus 2^{m-n} - 1, then induct.

2^20 - 1 = 1048575. Assume m > n and write 2^m - 1 = 2^{m-n}(2^n - 1) + (2^{m-n} - 1). Any common divisor of 2^m - 1 and 2^n - 1 therefore divides 2^{m-n} - 1, and the same identity read backwards gives the reverse, so gcd(2^m - 1, 2^n - 1) = gcd(2^{m-n} - 1, 2^n - 1). Repeating this step performs the Euclidean algorithm in the exponents, and by induction the process terminates at gcd(m, n), leaving the greatest common divisor 2^{gcd(m,n)} - 1. Since gcd(100, 60) = 20, the answer is 2^20 - 1 = 1048575. The result explains why Mersenne numbers with composite exponents are never prime beyond the trivial case: if d divides m properly, then 2^d - 1 is a proper divisor of 2^m - 1.

Follow-up: Does the same identity hold for a^m - 1 and a^n - 1 with a > 2, and what is gcd(2^m + 1, 2^n + 1)?

Key concepts: euclidean algorithm, greatest common divisor, mersenne numbers, induction.