PUMaC 2022 · 数论（B 组） · 第 5 题

PUMaC 2022 — Number Theory (Division B) — Problem 5

Given k ≥ 1, let p denote the k -th smallest prime number. If N is the number of ordered k 2023 Q 4-tuples ( a, b, c, d ) of positive integers satisfying abcd = p with a < b and c < d , find N k k =1 (mod 1000).

解析

Given k ≥ 1, let p denote the k -th smallest prime number. If N is the number of ordered k 2023 Q 4-tuples ( a, b, c, d ) of positive integers satisfying abcd = p with a < b and c < d , find N k k =1 (mod 1000). Proposed by Sunay Joshi 1 Answer: 112 We claim that if n ≥ 2 is square-free, then the number of ordered 4-tuples ( a, b, c, d ) satisfying 1 2 1 abcd = n with a < b and c < d is exactly τ ( n ) − τ ( n ). To see this, note that a 4-tuple 4 2 τ ( d ) 1 ( a, b, c, d ) coresponds to a choice of divisor d = ab of n . By symmetry, there are ways 1 2 τ ( n/d ) 1 to pick the pair ( a, b ) with a < b . Similarly there are ways to pick ( c, d ) with c < d . 2 P τ ( d ) τ ( n/d ) τ (1) τ ( n ) 1 1 Therefore the total number of 4-tuples is ( ) − 2 · · , where we subtract d | n 2 2 2 2 1 the terms corresponding to d = 1 , n . Since n is square-free, we have gcd( d , n/d ) = 1, hence 1 1 1 1 1 2 τ ( d ) τ ( n/d ) = τ ( n ) and the above reduces to τ ( n ) − τ ( n ), as claimed. 1 1 4 2 Q 2023 2023 Returning to the problem, note that for n = p , we have τ ( n ) = 2 , hence N = k k =1 2 · 2023 − 2 2023 − 1 2022 2022 2 − 2 = 2 (2 − 1). This is clearly 0 (mod 8). By Euler’s Theorem, we see 22 22 2 2 that N ≡ 2 (2 − 1) ≡ 48 (48 − 1) ≡ 112 (mod 125). By the Chinese Remainder Theorem, N ≡ 112 (mod 1000), our answer.