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 itscoefficients is 1. For any n ∈ N , f ( n ) is a multiple of 85. Find the smallest possible degree of f .
12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUNDthn
英文原题
[ 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 .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 th HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND
解析
英文解析
- [ 15 ] Let f be a polynomial with integer coefficients such that the greatest common divisor of all itscoefficients 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 coefficientssuch that g ( n ) ≡ 0 (mod p ) for some n , then g ( n + mp ) is divisible by p as well for any integermultiple mp of p . Therefore, it suffices to find the smallest possible degree of a polynomial f for whichf (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.
12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUNDthn