HMMT 十一月 2014 · GEN 赛 · 第 3 题

3. Compute the greatest common divisor of 4 − 1 and 8 − 1.

Answer: 15 Let d = gcd( a, b ) for some a, b ∈ Z . + Then, we can write d = ax − by , where x, y ∈ Z , and a ax 2 − 1 | 2 − 1 (1) b by 2 − 1 | 2 − 1 (2) d Multiplying the right-hand side of (2) by 2 , we get, b ax d 2 − 1 | 2 − 2 a b d gcd( a,b ) Thus, gcd(2 − 1 , 2 − 1) = 2 − 1 = 2 − 1. Using a = 16 and b = 36, we get 16 36 gcd(16 , 36) 4 gcd(2 − 1 , 2 − 1) = 2 − 1 = 2 − 1 = 15