PUMaC 2016 · 数论（A 组） · 第 7 题

PUMaC 2016 — Number Theory (Division A) — Problem 7

Compute the number of positive integers n between 2017 and 2017 such that n ≡ 1 (mod 2017). (2017 is prime.) 8 9 10 11

解析

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. 2 2