PUMaC 2023 · 团队赛 · 第 6 题

PUMaC 2023 — Team Round — Problem 6

Let f ( p ) denote the number of ordered tuples ( x , x , . . . , x ) of nonnegative integers satisfying 1 2 p p P P x = 2022, where x ≡ i (mod p ) for all 1 ≤ i ≤ p . Find the remainder when f ( p ) is i i p ∈S i =1 divided by 1000, where S denotes the set of all primes less than 2022.

解析

Let f ( p ) denote the number of ordered tuples ( x , x , . . . , x ) of nonnegative integers satisfying 1 2 p p P P x = 2022, where x ≡ i (mod p ) for all 1 ≤ i ≤ p . Find the remainder when f ( p ) is i i p ∈S i =1 divided by 1000, where S denotes the set of all primes less than 2022. Proposed by Sunay Joshi Answer: 475 p ( p − 1) Considering the equation modulo p , we see that ≡ 2022 (mod p ), hence p = 2 or 2 p | 2022 = 2 · 3 · 337. It is easy to see that p = 2 yields zero solutions. Further, p = 337 yields zero solutions because the left hand side is at least p ( p − 1) / 2. Hence the sum simplifies to f ( p ) for p = 3. Subtracting i from x for 1 ≤ i ≤ p − 1 and dividing by p , we find the equivalent i P 3 675 equation y = 673 for y ≥ 0. By stars and bars, this has solutions, which leaves a i i i =1 2 remainder of 475 when divided by 1000.