HMMT 二月 2025 · ALGNT 赛 · 第 9 题
HMMT February 2025 — ALGNT Round — Problem 9
题目详情
- Let f be the unique polynomial of degree at most 2026 such that for all n ∈ { 1 , 2 , 3 , . . . , 2027 } , ( 1 if n is a perfect square, f ( n ) = 0 otherwise. a 2025 Suppose that is the coefficient of x in f , where a and b are integers such that gcd( a, b ) = 1. b Compute the unique integer r between 0 and 2026 (inclusive) such that a − rb is divisible by 2027. (Note that 2027 is prime.)
解析
- Let f be the unique polynomial of degree at most 2026 such that for all n ∈ { 1 , 2 , 3 , . . . , 2027 } , ( 1 if n is a perfect square, f ( n ) = 0 otherwise. a 2025 Suppose that is the coefficient of x in f , where a and b are integers such that gcd( a, b ) = 1. b Compute the unique integer r between 0 and 2026 (inclusive) such that a − rb is divisible by 2027. (Note that 2027 is prime.) Proposed by: Pitchayut Saengrungkongka Answer: 1037 Solution 1: Let p = 2027. We work in F for the entire solution. Recall the well-known fact that p ( X − 1 if k > 0 and p − 1 | k, k x = 0 otherwise , x ∈ F p 0 n assuming 0 = 1. In particular, for any polynomial g ( x ) = b + b x + · · · + b x , we have 0 1 n X − g ( x ) = b + b + · · · + b . p − 1 2( p − 1) ⌊ n/ ( p − 1) ⌋ ( p − 1) x ∈ F p We apply this fact on g ( x ) = xf ( x ). As deg xf ( x ) ≤ p , the right hand side is simply the coefficient of 2025 x , which is what we want. Hence, the answer is X 45 · 46 · 91 2 2 2 − xf ( x ) = − (1 + 2 + · · · + 45 ) = − ≡ 1037 (mod 2027) . 6 x ∈ F p Solution 2: Again, let p = 2027 and work in F . By the Lagrange Interpolation formula, we get that p X Y x − j f ( x ) = f ( i ) . i − j i ∈ F j ̸ = i p We now simplify the polynomial in the product sign on the right-hand side. First, recall the identity Y p p ( x − j ) = x − x = ( x − i ) − ( x − i ) . j ∈ F p Q The denominator ( i − j ) becomes ( p − 1)! = − 1 by Wilson’s. Thus, we get that j ̸ = i p Y x − j ( x − i ) − ( x − i ) p − 1 = − = − ( x − i ) + 1 . i − j x − i j ̸ = i p − 2 The coefficient of x in the above expression is − i . Therefore, the first equation gives that the p − 2 coefficient of x in f ( x ) is X 45 · 46 · 91 2 2 2 − if ( i ) = − (1 + 2 + · · · + 45 ) = − ≡ 1037 (mod 2027) . 6 i ∈ F p