PUMaC 2022 · 数论（A 组） · 第 7 题
PUMaC 2022 — Number Theory (Division A) — Problem 7
题目详情
- For a positive integer n , let f ( n ) be the number of integers m satisfying 0 ≤ m ≤ n − 1 such 2 that there exists an integer solution to the congruence x ≡ m (mod n ). It is given that as k k k goes to ∞ , the value of f (225 ) / 225 converges to some rational number p/q , where p, q are relatively prime positive integers. Find p + q .
解析
- For a positive integer n , let f ( n ) be the number of integers m satisfying 0 ≤ m ≤ n − 1 such 2 that there exists an integer solution to the congruence x ≡ m (mod n ). It is given that as k k k goes to ∞ , the value of f (225 ) / 225 converges to some rational number p/q , where p, q are relatively prime positive integers. Find p + q . Proposed by Frank Lu Answer: 37 First, suppose that m, n are relatively prime. Then, notice that for every pair of residues a 2 2 (mod m ) and b (mod n ) , if x ≡ a (mod m ) and x ≡ b (mod n ) both have solutions, then the corresponding residue r modulo mn (through using Chinese Remainder Theorem) is such 2 that x ≡ r (mod mn ) . Similarly, if there is a solution for this residue, then there is such a solution for the residues of r (mod m ) and r (mod n ) . Therefore, f ( mn ) = f ( m ) f ( n ) . It thus 2 k 2 k suffices for us to compute f (5 ) and f (3 ) . We will perform this computation in generality for a prime p. 2 2 k 2 k Suppose that x ≡ b (mod p ) has a solution, where 0 ≤ b < p . Then, notice that if b is 2 ′ 2 divisible by p, then it is divisible by p . From here, it follows that, writing b = b p , we must 2 ′ 2 k 2 k have a solution to x ≡ b (mod p ) . Therefore, using this logic, f ( p ) is equal to the sum 2 2 i of the number of residues b relatively prime to p so that x ≡ b (mod p ) has a solution, for 0 ≤ i ≤ k. For i = 0 there is exactly one such solution, namely b ≡ 1 (mod 1) . Now, we claim that 2 i − 1 there are p ( p − 1) / 2 such solutions for i. To show this, we inductively argue the following: 2 i given p > 2 is a prime and b relatively prime to p, if x ≡ b (mod p ) has a solution, then 2 i i +1 ′ x ≡ b + cp (mod p ) has a solution for c = 0 , 1 , . . . , p − 1 . Indeed, observe that, given x so 2 2 ′ i ′ i i +1 ′ i 2 i ′ i x ≡ b (mod p ) , suppose that x ≡ b + ap (mod p ) . Then, ( x + dp ) ≡ b + ap + 2 x dp i +1 i i +1 ′ (mod p ) . For this to equal b + cp modulo p , we need for x d + a ≡ c (mod p ) . But as b ′ is relatively prime to p, so is x ; therefore this has exactly one such solution. i +1 In particular, this means that p has p times as many residues b satisfying the above condition i i i − 1 than p . So recalling that for p there are ( p − 1) / 2 such residues, it follows that p has p ( p −