PUMaC 2019 · 数论（B 组） · 第 2 题

PUMaC 2019 — Number Theory (Division B) — Problem 2

The least common multiple of two positive integers a and b is 2 × 3 . How many such ordered pairs ( a, b ) are there?

解析

101 | f (0) + f (1) + f (2) + · · · + f (100). Compute the remainder when f (101) is divided by 2 101 . Proposed by: Matthew Kendall Answer: 203 We use this fact: For nonnegative integer k and prime p > 2, 2 2 k +1 2 k +1 2 k +1 p | 1 + 2 + · · · + ( p − 1) . 2 k +1 2 k +1 2 This comes from j + ( p − j ) ≡ (2 k + 1) jp (mod p ) and summing over all j . Let p = 101. Plugging n = 0 into 1 gives f (0) = 1. Since deg f = 2019, we can write f ( n ) = 1 + an + g ( n ) where g is odd and all of its terms are of degree at least 3. Now using 2 fact 2, p | g (0) + g (1) + g (2) + · · · + g ( p ). This means 2 f (0) + f (1) + f (2) + · · · + f (100) ≡ p + a (1 + · · · + ( p − 1)) . (mod p ) 2 2 2 So 2 p + ap ( p − 1) ≡ 0 (mod p ) or ap ≡ 2 p (mod p ). Hence, f ( p ) = 1 + ap ≡ 2 p + 1 (mod p ). 2 Plugging in p = 101 gives f (101) ≡ 203 (mod 101 ). 2 ∑ n