HMMT 二月 2015 · 冲刺赛 · 第 19 题
HMMT February 2015 — Guts Round — Problem 19
题目详情
- [ 11 ] Find the smallest positive integer n such that the polynomial ( x + 1) − 1 is “divisible by x + 1 modulo 3”, or more precisely, either of the following equivalent conditions holds: n 2 • there exist polynomials P, Q with integer coefficients such that ( x +1) − 1 = ( x +1) P ( x )+3 Q ( x ); n • or more conceptually, the remainder when (the polynomial) ( x + 1) − 1 is divided by (the 2 polynomial) x + 1 is a polynomial with (integer) coefficients all divisible by 3.
解析
- [ 11 ] Find the smallest positive integer n such that the polynomial ( x + 1) − 1 is “divisible by x + 1 modulo 3”, or more precisely, either of the following equivalent conditions holds: n 2 • there exist polynomials P, Q with integer coefficients such that ( x +1) − 1 = ( x +1) P ( x )+3 Q ( x ); n • or more conceptually, the remainder when (the polynomial) ( x + 1) − 1 is divided by (the 2 polynomial) x + 1 is a polynomial with (integer) coefficients all divisible by 3. 2 2 4 2 Answer: 8 Solution 1. We have ( x + 1) = x + 2 x + 1 ≡ 2 x , ( x + 1) ≡ (2 x ) ≡ − 4 ≡ − 1, and 8 2 2 ( x + 1) ≡ ( − 1) = 1. So the order n divides 8, as x + 1 and x + 1 are relatively prime polynomials modulo 3 (or more conceptually, in F [ x ]), but cannot be smaller by our computations of the 2nd and 3 4th powers. Remark. This problem illustrates the analogy between integers and polynomials (specifically here, 2 polynomials over the finite field of integers modulo 3), with x + 1 (mod 3) taking the role of a 2 deg( x +1) 3 prime number. Indeed, we can prove analogously to Fermat’s little theorem that f ( x ) ≡ f ( x ) 2 (mod x + 1 , 3) for any polynomial f ( x ): try to work out the proof yourself! (This kind of problem, 2 with 3 replaced by any prime p and x + 1 by any irreducible polynomial modulo p , is closely related to the theory of (extensions of ) finite fields .) n Solution 2. Here’s a solution avoiding the terminology of groups and fields. Let R ( x ) = ( x + 1) − 1 − 2 P ( x )( x + 1) = 3 Q ( x ) be the remainder (here P is the quotient), whose coefficients (upon expansion) must all be divisible by 3. Now consider R ( i ). The coefficients of the even and odd powers of x are 2 divisible by 3, so R ( i ) must have real and imaginary parts divisible by 3. Notice that (1 + i ) = 2 i , 4 6 8 8 (1 + i ) = − 4, (1 + i ) = − 8 i , (1 + i ) = 16, and that (1 + i ) − 1 = 15, which has real and imaginary parts divisible by 3. Since any even power of (1 + i ) (for n ≤ 6) yields a purely real or purely imaginary number with a coefficient not divisible by 3, multiplying it by 1 + i will yield an imaginary part not divisible by 3. To see that n = 8 works, notice that, when taken modulo 3, 8 8 7 6 5 4 3 2 ( x + 1) − 1 = x + 8 x + 28 x + 56 x + 70 x + 56 x + 28 x + 8 x 8 7 6 5 4 3 2 ≡ x − x + x − x + x − x + x − x 2 6 5 2 = ( x + 1)( x − x + x − x ) (mod 3) , as desired.