HMMT 二月 2015 · 冲刺赛 · 第 19 题

英文解析

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 );
    • or more conceptually, the remainder when (the polynomial) ( x + 1) − 1 is divided by (thenpolynomial) x + 1 is a polynomial with (integer) coefficients all divisible by 3.2
    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 polynomialsmodulo 3 (or more conceptually, in F [ x ]), but cannot be smaller by our computations of the 2 nd and
    4 th powers.3
    Remark. This problem illustrates the analogy between integers and polynomials (specifically here,
    polynomials over the finite field of integers modulo 3), with x + 1 (mod 3) taking the role of a 2
    deg( x +1)2
    prime number. Indeed, we can prove analogously to Fermat’s little theorem that f ( x ) ≡ f ( x )3
    (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 2
    to the theory of (extensions of ) finite fields .)
    Solution 2. Here’s a solution avoiding the terminology of groups and fields. Let R ( x ) = ( x + 1) − 1 −n
    P ( x )( x + 1) = 3 Q ( x ) be the remainder (here P is the quotient), whose coefficients (upon expansion)2
    must all be divisible by 3. Now consider R ( i ). The coefficients of the even and odd powers of x aredivisible by 3, so R ( i ) must have real and imaginary parts divisible by 3. Notice that (1 + i ) = 2 i ,2
    4 6 8 8
    (1 + i ) = − 4, (1 + i ) = − 8 i , (1 + i ) = 16, and that (1 + i ) − 1 = 15, which has real and imaginaryparts divisible by 3. Since any even power of (1 + i ) (for n ≤ 6) yields a purely real or purely imaginarynumber with a coefficient not divisible by 3, multiplying it by 1 + i will yield an imaginary part notdivisible 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.