PUMaC 2016 · 数论（B 组） · 第 8 题
PUMaC 2016 — Number Theory (Division B) — Problem 8
题目详情
- Compute the number of positive integers n between 2017 and 2017 such that n ≡ 1 (mod 2017). (2017 is prime.) 1
解析
- Ignore 2017 — clearly it’s not among the integers with the desired property. Among the rest, for every ( a, b ) there is exactly one integer that is a modulo 2017 and b modulo 2016, n b and we may treat n as a for the appropriate a and b , by Fermat’s little theorem. Thus, we are looking for the number of pairs ( a, b ) of integers with 0 ≤ a < 2017 and 0 ≤ b < 2016 b such that a ≡ 1 (mod 2017). Now, the multiplicative group of integers modulo 2017 is cyclic 0 1 2015 and its order is 2016. Write this group as g , g , . . . , g . Written this way, it is clear that kb we are looking for the number of pairs ( k, b ) of integers 0 ≤ k, b < 2016 such that g ≡ 1 (mod 2017), i.e. kb | 2016. Enumerating over b , we note that this condition is satisfied if 2016 and only if k is divisible by (and there are gcd( b, 2016) such values of k ). Thus gcd( b, 2016) we are looking for the sum over 0 ≤ b < 2016 of gcd( b, 2016). We note that this gcd-sum function (which we will denote g , i.e. we are looking for g (2016)) is multiplicative, because gcd( k, m ) gcd( k, n ) = gcd( k, mn ) for relatively prime m and n , and so g (2016) = g (32) g (9) g (7). These three quantities can be easily evaluated, and are equal to 112, 21, and 13, respectively, and so our answer is 112 · 21 · 13 = 30576 . 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. 2