HMMT 十一月 2011 · 冲刺赛 · 第 11 题

HMMT November 2011 — Guts Round — Problem 11

[ 8 ] For positive integers m, n , let gcd( m, n ) denote the largest positive integer that is a factor of both m and n . Compute 91 ∑ gcd( n, 91) . n =1

解析

[ 8 ] For positive integers m, n , let gcd( m, n ) denote the largest positive integer that is a factor of both m and n . Compute 91 ∑ gcd( n, 91) . n =1 Answer: 325 Since 91 = 7 × 13, we see that the possible values of gcd( n, 91) are 1 , 7 , 13 , 91. For 1 ≤ n ≤ 91, there is only one value of n such that gcd( n, 91) = 91 . Then, we see that there are 12 values of n for which gcd( n, 91) = 7 (namely, multiples of 7 other than 91), 6 values of n for which gcd( n, 91) = 13 (the multiples of 13 other than 91), and 91 − 1 − 6 − 12 = 72 values of n for which gcd( n, 91) = 1. Hence, our answer is 1 × 91 + 12 × 7 + 6 × 13 + 72 × 1 = 325.