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

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

Let n be the number of polynomial functions from the integers modulo 2010 to the integers modulo 2010. n can be written as n = p p · · · p , where the p s are (not necessarily distinct) 1 2 k i primes. Find p + p + · · · + p . 1 2 n 2 2 2

解析

Let I = { 0 , 1 , 2 , . . . 2008 , 2009 } , and let S = { f : I → I | f ( a ) ≡ g ( a )(mod 2010) ∀ a } , where g ( a ) ranges over all polynomials with integer coefficients. The number of elements in S can be written as p p · · · p , where the p s are (not necessarily distinct) primes. Find p + p + · · · + p . 1 2 k i 1 2 n Solution: Any polynomial is determined, by the Chinese remainder theorem, by its restriction 2 3 5 67 to the integers mod 2, 3, 5, and 67. There are thus at most 2 · 3 · 5 · 67 such functions. However, if you have a polynomial in those various moduli, then there is a polynomial that 2 3 5 67 restricts to those polynomials, so there are at least 2 · 3 · 5 · 67 such functions and thus 2 3 5 67 exactly 2 · 3 · 5 · 67 such functions. The answer is then 4527. 1 2 2 2