HMMT 二月 2015 · 代数 · 第 8 题

英文解析

8. Find the number of ordered pairs of integers ( a, b ) ∈ { 1 , 2 , . . . , 35 } (not necessarily distinct) such thatax + b is a “quadratic residue modulo x + 1 and 35”, i.e. there exists a polynomial f ( x ) with integer 2
   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 );
   • 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.2
   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).
   First we do the modulo 7 case . Since x + 1 is irreducible modulo 7 (or more conceptually, in F [ x ]),2
   2 27
   exactly half of the nonzero residues modulo x + 1 and 7 (or just modulo x + 1 if we’re working in
   7 − 12
   F [ x ]) are quadratic residues, i.e. our answer is 1 + = 25 (where we add back one for the zeropolynomial).27
   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 2
   5 5
   the product of the number of polynomial quadratic residues modulo x ± 2. By centering/evaluatingpolynomials 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.
   Our final answer is thus 25 · 9 = 225.2
   Remark. This problem illustrates the analogy between integers and polynomials (specifically here,
   polynomials over the finite field of integers modulo 5 or 7), with x + 1 (mod 7) or x ± 2 (mod 5)2
   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