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)
   Multiplying the right-hand side of (2) by 2 , we get,db 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