HMMT 二月 2016 · 团队赛 · 第 2 题
HMMT February 2016 — Team Round — Problem 2
题目详情
- [ 25 ] For positive integers n , let c be the smallest positive integer for which n − 1 is divisible by 210, n if such a positive integer exists, and c = 0 otherwise. What is c + c + · · · + c ? n 1 2 210 ◦
解析
- [ 25 ] For positive integers n , let c be the smallest positive integer for which n − 1 is divisible by 210, n if such a positive integer exists, and c = 0 otherwise. What is c + c + · · · + c ? n 1 2 210 Proposed by: Joy Zheng Answer: 329 In order for c 6 = 0, we must have gcd( n, 210) = 1, so we need only consider such n . The number n c n n − 1 is divisible by 210 iff it is divisible by each of 2, 3, 5, and 7, and we can consider the order of n modulo each modulus separately; c will simply be the LCM of these orders. We can ignore the n modulus 2 because order is always 1. For the other moduli, the sets of orders are a ∈ { 1 , 2 } mod 3 b ∈ { 1 , 2 , 4 , 4 } mod 5 c ∈ { 1 , 2 , 3 , 3 , 6 , 6 } mod 7 . By the Chinese Remainder Theorem, each triplet of choices from these three multisets occurs for exactly one n in the range { 1 , 2 , . . . , 210 } , so the answer we seek is the sum of lcm( a, b, c ) over a , b , c in the Cartesian product of these multisets. For a = 1 this table of LCMs is as follows: 1 2 3 3 6 6 1 1 2 3 3 6 6 2 2 2 6 6 6 6 4 4 4 12 12 12 12 4 4 4 12 12 12 12 which has a sum of 21 + 56 + 28 + 56 = 161. The table for a = 2 is identical except for the top row, where 1 , 3 , 3 are replaced by 2 , 6 , 6, and thus has a total sum of 7 more, or 168. So our answer is 161 + 168 = 329 . This can also be computed by counting how many times each LCM occurs: • 12 appears 16 times when b = 4 and c ∈ { 3 , 6 } , for a contribution of 12 × 16 = 192; • 6 appears 14 times, 8 times when c = 6 and b ≤ 2 and 6 times when c = 3 and ( a, b ) ∈ { (1 , 2) , (2 , 1) , (2 , 2) } , for a contribution of 6 × 14 = 84; • 4 appears 8 times when b = 4 and a, c ∈ { 1 , 2 } , for a contribution of 4 × 8 = 32; • 3 appears 2 times when c = 3 and a = b = 1, for a contribution of 3 × 2 = 6; • 2 appears 7 times when a, b, c ∈ { 1 , 2 } and ( a, b, c ) 6 = (1 , 1 , 1), for a contribution of 2 × 7 = 14; • 1 appears 1 time when a = b = c = 1, for a contribution of 1 × 1 = 1. The result is again 192 + 84 + 32 + 6 + 14 + 1 = 329. ◦