PUMaC 2019 · 数论（A 组） · 第 1 题

PUMaC 2019 — Number Theory (Division A) — Problem 1

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

解析

But some residue a mod 2019 must appear infinitely many times, which gives us a ≡ 1 (mod 2019), as desired. Claim 3: Let n be the minimal compact number. Then all compact numbers are multiples of n , and conversely any multiple of n is a good number. Proof: Let N be another compact number, and suppose N = nq + r , but then we have N r a ≡ a ≡ 1 which would make r the minimal good number, a contradiction unless r = 0. The other direction is trivial. Claim 4: The minimal compact number is 672. 2 · 672 Proof: Let x and y be primitive roots modulo 3 and 673. Then the order of xy is = 672, (2 , 672) 672 672 so the minimal compact number is at least 672. Note, a ≡ 1 (mod 3) and a ≡ 1 672 (mod 673) therefore a ≡ 1 (mod 2019) for all ( a, 2019) = 1. Therefore the minimal compact number is 672. Therefore, the sum is 672 · (1 + 2 + 3 + 4 + 5 + 6) = 672 · 21 = 14112. p q − 1