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

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

Call a positive integer n compact if for any infinite sequence of distinct primes p , p , . . . there 1 2 exists a finite subsequence of n primes p , p , . . . p (where the x are distinct) such that x x x i 1 2 n p p · · · p ≡ 1 (mod 2019) x x x 1 2 n Find the sum of all compact numbers less than 2 · 2019. p q − 1

解析

Call a positive integer n compact if for any infinite sequence of distinct primes p , p , . . . there 1 2 exists a finite subsequence of n primes p , p , . . . p (where the x are distinct) such that x x x i 1 2 n p p · · · p ≡ 1 (mod 2019) x x x 1 2 n Find the sum of all compact numbers less than 2 · 2019. Proposed by: Rahul Saha Answer: 14112 n Claim 1: Let n be a compact number. Then we must have a ≡ 1 (mod 2019) for all ( a, 2019) = 1. Proof: By Dirichlet’s theorem on arithmetic progressions, we can find infinitely many primes p ≡ a (mod 2019). Letting our sequence be composed only of these primes, we must have n a ≡ 1 (mod 2019). n Claim 2: If a ≡ 1 (mod 2019) for all ( a, 2019) = 1, then n is a compact number. Proof: Note that by taking all large enough primes in our sequence, we can assume ( p , 2019) = i n