HMMT 二月 2024 · ALGNT 赛 · 第 10 题
HMMT February 2024 — ALGNT Round — Problem 10
题目详情
- A polynomial f ∈ Z [ x ] is called splitty if and only if for every prime p , there exist polynomials g , h ∈ Z [ x ] with deg g , deg h < deg f and all coefficients of f − g h are divisible by p . Compute p p p p p p 4 2 the sum of all positive integers n ≤ 100 such that the polynomial x + 16 x + n is splitty.
解析
- A polynomial f ∈ Z [ x ] is called splitty if and only if for every prime p , there exist polynomials g , h ∈ Z [ x ] with deg g , deg h < deg f and all coefficients of f − g h are divisible by p . Compute p p p p p p 4 2 the sum of all positive integers n ≤ 100 such that the polynomial x + 16 x + n is splitty. Proposed by: Pitchayut Saengrungkongka Answer: 693 4 2 2 Solution: We claim that x + ax + b is splitty if and only if either b or a − 4 b is a perfect square. 2 2 (The latter means that the polynomial splits into ( x − r )( x − s )). Assuming the characterization, one can easily extract the answer. For a = 16 and b = n , one of n and 64 − n has to be a perfect square. The solutions to this that are at most 64 form 8 pairs that sum to 64 (if we include 0), and then we additionally have 81 and 100. This means the sum is 64 · 8 + 81 + 100 = 693 . Now, we move on to prove the characterization. Necessity. 2 Take a prime p such that neither a − 4 b nor b is a quadratic residue modulo p (exists by Dirichlet + CRT + QR). Work in F . Now, suppose that p 4 2 2 2 x + ax + b = ( x + mx + n )( x + sx + t ) . 3 Then, looking at the x -coefficient gives m + s = 0 or s = − m . Looking at the x -coefficient gives m ( n − t ) = 0. 4 2 2 2 2 2 2 • If m = 0, then s = 0, so x + ax + b = ( x + n )( x + t ), which means a − 4 b = ( n + t ) − 4 nt = ( n − t ) , a quadratic residue modulo p , contradiction. • If n = t , then b = nt is a square modulo p , a contradiction. (The major surprise of this problem is that this suffices, which will be shown below.) Sufficiency. 4 2 2 2 Clearly, the polynomial splits in p = 2 because in F [ x ], we have x + ax + b = ( x + ax + b ) . Now, 2 assume p is odd. 2 4 2 2 2 If a − 4 b is a perfect square, then x + ax + b splits into ( x − r )( x − s ) even in Z [ x ]. 2 If b is a perfect square, then let b = k . We then note that ( ) 2 2 4 2 2 2 a − 4 k • x + ax + b splits in form ( x − r )( x − s ) if = 1. p ( ) 2 k − a 4 2 2 2 2 • x + ax + b splits in form ( x + rx + k )( x − rx + k ) if a = 2 k − r , or = 1. p ( ) − 2 k − a 4 2 2 2 2 • x + ax + b splits in form ( x + rx − k )( x − rx − k ) if a = − 2 k − r , or = 1. p 2 2 Since (2 k − a )( − 2 k − a ) = a − 4 k , it follows that at least one of these must happen.