PUMaC 2016 · 团队赛 · 第 3 题

PUMaC 2016 — Team Round — Problem 3

(4) Compute the sum of all positive integers n < 200 such that gcd( n, k ) 6 = 1 for every k ∈ { 2 · 11 · 19 , 3 · 13 · 17 , 5 · 11 · 13 , 7 · 17 · 19 } .

解析

Clearly n must have factors in each of { 2 , 11 , 19 } , { 3 , 13 , 17 } , { 5 , 11 , 13 } , and { 7 , 17 , 19 } . If n 19 | n then must have a factor in common with both 3 · 13 · 17 and 5 · 11 · 13, so n is at least 19 n 19 · 13, which is impossible since n < 200. If 17 | n then must have a factor in common with 17 n both 2 · 11 · 19 and 5 · 11 · 13, and note that ≤ 11. This gives two possibilities: 17 · 10 = 170 17 n and 17 · 11 = 187. If n is divisible by 13 then must have a factor in common with both 13 2 · 11 · 19 and 7 · 17 · 19. This gives n = 13 · 14 = 182. If n does not divide any of 13, 17, and 19 then it is easy to see that n must be divisible by 3 and 7. Then n must also have a factor in n common with 2 · 11 · 19 and 5 · 11 · 13, which means that ≥ 10, which is impossible. Thus, 21 the answer is 170 + 182 + 187 = 539 . Problem written by Eric Neyman. k k