HMMT 二月 2015 · 代数 · 第 8 题
HMMT February 2015 — Algebra — Problem 8
题目详情
- Find the number of ordered pairs of integers ( a, b ) ∈ { 1 , 2 , . . . , 35 } (not necessarily distinct) such that 2 ax + b is a “quadratic residue modulo x + 1 and 35”, i.e. there exists a polynomial f ( x ) with integer coefficients such that either of the following equivalent conditions holds: 2 2 • there exist polynomials P, Q with integer coefficients such that f ( x ) − ( ax + b ) = ( x + 1) P ( x ) + 35 Q ( x ); 2 • or more conceptually, the remainder when (the polynomial) f ( x ) − ( ax + b ) is divided by (the 2 polynomial) x + 1 is a polynomial with (integer) coefficients all divisible by 35. 2015 4
解析
- Find the number of ordered pairs of integers ( a, b ) ∈ { 1 , 2 , . . . , 35 } (not necessarily distinct) such that 2 ax + b is a “quadratic residue modulo x + 1 and 35”, i.e. there exists a polynomial f ( x ) with integer coefficients such that either of the following equivalent conditions holds: 2 2 • there exist polynomials P, Q with integer coefficients such that f ( x ) − ( ax + b ) = ( x + 1) P ( x ) + 35 Q ( x ); 2 • or more conceptually, the remainder when (the polynomial) f ( x ) − ( ax + b ) is divided by (the 2 polynomial) x + 1 is a polynomial with (integer) coefficients all divisible by 35. Answer: 225 By the Chinese remainder theorem, we want the product of the answers modulo 5 and modulo 7 (i.e. when 35 is replaced by 5 and 7, respectively). 2 First we do the modulo 7 case . Since x + 1 is irreducible modulo 7 (or more conceptually, in F [ x ]), 7 2 2 exactly half of the nonzero residues modulo x + 1 and 7 (or just modulo x + 1 if we’re working in 2 7 − 1 F [ x ]) are quadratic residues, i.e. our answer is 1 + = 25 (where we add back one for the zero 7 2 polynomial). 2 Now we do the modulo 5 case . Since x + 1 factors as ( x + 2)( x − 2) modulo 5 (or more conceptually, 2 in F [ x ]), by the polynomial Chinese remainder theorem modulo x + 1 (working in F [ x ]), we want 5 5 the product of the number of polynomial quadratic residues modulo x ± 2. By centering/evaluating polynomials at ∓ 2 accordingly, the polynomial squares modulo these linear polynomials are just those 5 − 1 4 2 reducing to integer squares modulo 5. So we have an answer of (1 + ) = 9 in this case. 2 Our final answer is thus 25 · 9 = 225. Remark. This problem illustrates the analogy between integers and polynomials (specifically here, 2 polynomials over the finite field of integers modulo 5 or 7), with x + 1 (mod 7) or x ± 2 (mod 5) taking the role of a prime number. Indeed, just as in the integer case, we expect exactly half of the (coprime) residues to be (coprime, esp. nonzero) quadratic residues. 2015 4