PUMaC 2016 · 团队赛 · 第 15 题
PUMaC 2016 — Team Round — Problem 15
题目详情
- (12) Compute the sum of all positive integers n with the property that x ≡ 1 (mod 2016) has n solutions in { 0 , 1 , 2 , . . . , 2015 } . 3
解析
- Note that x ≡ 1 (mod 2016) if and only if x ≡ 1 (mod 32) and x ≡ 1 (mod 9) and x ≡ 1 2 3 4 5 k (mod 7). Write the integers modulo 7 relatively prime to 7 as { 1 , 3 , 3 , 3 , 3 , 3 } . If x ≡ 3 n (mod 7) then x ≡ 1 (mod 7) if and only if kn ≡ 1 (mod 6), which happens for gcd( n, 6) values of k (and therefore x ) modulo 7. The same holds modulo 9, because we can write 2 3 4 5 the integers modulo 9 relatively prime to 9 as { 1 , 2 , 2 , 2 , 2 , 2 } (so again there are gcd( n, 6) possible values of x modulo 9). The value of x modulo 32 is more difficult to deal with. We find that the numbers modulo 32 k k relatively 32 can be written as { 3 , 5 · 3 | k ∈ { 0 , 1 , . . . , 7 }} . From this structure we find that there is one element of order 1, three of order 2, four of order 4, and eight of order 8. Thus, if n is odd there is 1 value of x modulo 32; 4 if n is divisible by 2 but not 4; 8 if n is divisible by 4 but not 8; and 16 if n is divisible by 8. 2 Thus, the total number of values of x in { 0 , 1 , . . . , 2015 } is gcd ( n, 6) times either 1, 4, 8, or k m 16; and this value must equal n , so n is of the form 2 3 . From our formula for the number of values of x we conclude that m is either 0 or 2 and k is either 0 or 6. Thus, the answer is 1 + 9 + 64 + 64 · 9 = (1 + 9)(1 + 64) = 650 . Problem written by Eric Neyman. If you believe that any of these answers is incorrect, or that a problem had multiple reason- able interpretations or was incorrectly stated, you may appeal at tinyurl.com/pumacappeals . All appeals must be in by 1 PM to be considered. 4