HMMT 二月 2009 · 冲刺赛 · 第 30 题

HMMT February 2009 — Guts Round — Problem 30

[ 15 ] Let f be a polynomial with integer coefficients such that the greatest common divisor of all its coefficients is 1. For any n ∈ N , f ( n ) is a multiple of 85. Find the smallest possible degree of f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND n

解析

[ 15 ] Let f be a polynomial with integer coefficients such that the greatest common divisor of all its coefficients is 1. For any n ∈ N , f ( n ) is a multiple of 85. Find the smallest possible degree of f . Answer: 17 Solution: Notice that, if p is a prime and g is a polynomial with integer coefficients such that g ( n ) ≡ 0 (mod p ) for some n , then g ( n + mp ) is divisible by p as well for any integer multiple mp of p . Therefore, it suffices to find the smallest possible degree of a polynomial f for which f (0) , f (1) , f (2) , . . . , f (16) are divisible by 17 and by 5. There is a polynomial of degree 17 with integer coefficients having f (0) = f (1) = · · · = f (16) = 0, namely f ( x ) = ( x )( x − 1)( x − 2) · · · ( x − 16). Thus the minimal degree is no larger than 17. Now, let f be such a polynomial and consider f modulo 17. The polynomial has 17 roots, so it must be at least degree 17 when taken modulo 17. Thus f has degree at least 17 as well. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND n