PUMaC 2022 · 数论（A 组） · 第 4 题

PUMaC 2022 — Number Theory (Division A) — Problem 4

Find the number of ordered pairs ( x, y ) of integers with 0 ≤ x < 2023 and 0 ≤ y < 2023 such 3 2 that y ≡ x (mod 2023).

解析

Find the number of ordered pairs ( x, y ) of integers with 0 ≤ x < 2023 and 0 ≤ y < 2023 such 3 2 that y ≡ x (mod 2023). Proposed by Brandon Cho Answer: 3927 1 2 Since 2023 = 7 · 17 , by the Chinese Remainder Theorem it suffices to consider the pair of 3 2 3 2 2 congruences y ≡ x (mod 7) and y ≡ x (mod 17 ). 2 3 3 2 For the former, note that since x ∈ { 0 , 1 , 2 , 4 } and y ∈ { 0 , 1 , − 1 } , we must have y ≡ x ≡ 0 3 2 or y ≡ x ≡ 1. The former corresponds to (0 , 0). The latter is satisfied when x ∈ { 1 , − 1 } and y ∈ { 1 , 2 , 4 } . This yields 6 pairs. Thus this case has 7 solutions. For the latter congruence, we consider two cases. The first case is when 17 does not divide 3 y , so that 17 does not divide x . Further the map y 7 → y is a bijection of the set of units of 2 Z / 17 Z . Therefore each choice of unit x corresponds to a unique solution for y . Since there 2 2 2 are 17 − 17 units mod 17 , we have a total of 17 − 17 pairs in this case. The second case is when 17 divides y , hence 17 divides x . Any such pair ( x, y ) satisfies the congruence since both sides are 0. It follows that there are 17 · 17 pairs in this third case. Summing, we find 2 2 · 17 − 17 pairs. Finally, we multiply the number of solutions to each of the two congruences to find an answer 2 of 7 · (2 · 17 − 17) = 3927.