HMMT 十一月 2024 · 团队赛 · 第 10 题
HMMT November 2024 — Team Round — Problem 10
题目详情
- [55] For each positive integer n , let f ( n ) be either the unique integer r ∈ { 0 , 1 , . . . , n − 1 } such that n divides 15 r − 1 , or 0 if such r does not exist. Compute f (16) + f (17) + f (18) + · · · + f (300) .
解析
- [55] For each positive integer n , let f ( n ) be either the unique integer r ∈ { 0 , 1 , . . . , n − 1 } such that n divides 15 r − 1, or 0 if such r does not exist. Compute f (16) + f (17) + f (18) + · · · + f (300) . Proposed by: Jordan Lefkowitz, Pitchayut Saengrungkongka Answer: 11856 Solution: Note we only need to sum f ( n ) for n relatively prime to 15. For any such n > 1, there exists a positive integer b such that 15 f ( n ) − 1 = bn . Since bn ≤ 15( n − 1) − 1 < 15 n it follows that b ∈ { 1 , . . . , 14 } . Moreover, we have bn ≡ 1 (mod 15). These two conditions uniquely determine b . Now, we are in business to compute the sum. Let S be the set of positive integers a ∈ { 0 , 1 , 2 , . . . , 14 } such that gcd( a, 15) = 1. For each a ∈ S , we first sum f ( n ) over n = 15 k + a for k ∈ { 1 , 2 , . . . , 19 } . Given a , we can uniquely determine b from b ≡ − 1 /a (mod 15). Thus, the sum of f ( n ) across all numbers of the form n = 15 k + a is 19 19 X X b (15 k + a ) + 1 f (15 k + a ) = 15 k =1 k =1 19 X ab + 1 = 19 · + b k 15 k =0 ab + 1 = 19 · + 190 b. 15 We now sum the above expression across all a ∈ S . ab +1 • The sum of the first term 19 · needs to be evaluated manually. The pairs ( a, b ) that works 15 are (1 , 14), (2 , 7), (4 , 11), (8 , 13), and four other pairs obtained by swapping a and b . Thus, the sum of the first term over all a ∈ S is 1 · 14+1 2 · 7+1 4 · 11+1 8 · 13+1 19 · 2 · + + + = 19 · 2 · (1 + 1 + 3 + 7) = 456 . 15 15 15 15 • To evaluate the sum of the second term 190 b , we note that as a varies through S , b attains every value in S exactly once. We have | S | = φ (15) = 8 and b ∈ S ⇐⇒ 15 − b ∈ S , so the sum of 15 · 8 elements of S is = 60. Hence, the sum of the second term over all a ∈ S is 190 · 60 = 11400. 2 Hence, the answer is 11400 + 456 = 11856 . Remark. Two versions of this problem were submitted independently (!) by Jordan Lefkowitz and Pitchayut Saengrungkongka within a few hours. The version that was selected for the exam is Pitchayut’s. The following is Jordan’s problem: For integers 2 ≤ n ≤ 100, let f ( n ) denote the unique integer 1 ≤ a < n such that 101 a ≡ 1 (mod n ). Estimate 100 X f ( n ) . n n =2