Maths Olympiad Prep

Library / /29 of 62

Number theory Difficulty 5.5 AIME, harder Prove it Ukraine

Let f(x)=ax2+bx+cf(x) = ax^2 + bx + c be a polynomial with integer coefficients. For every integer xx f(x)f(x) is divisible by NN where NN is a positive integer. Is it true that NN necessarily divides all the coefficients of f(x)f(x) if
a) N=2016;b) N=2017? \text{a) } N = 2016; \quad \text{b) } N = 2017?

Solution

a) Note that for any integer xx the product x(x+1)x(x+1) is even. This suggests the following example:
1008x(x+1)+2016=1008x2+1008x+2016. 1008x(x+1)+2016=1008x^2+1008x+2016.
For every integer xx, f(x)f(x) is divisible by 20162016, but 20162016 does not divide all the coefficients (10081008 is not divisible by 20162016). Thus, the answer is no.

b) We have f(x)=ax2+bx+cf(x) = ax^2 + bx + c. Let us do the following substitutions:
x=0f(0)=c    2017c;x=1f(1)=a+b+c    2017a+b+c;x=1f(1)=ab+c    2017ab+c. \begin{aligned} x &= 0 \Rightarrow f(0) = c \implies 2017 \,|\, c; \\ x &= 1 \Rightarrow f(1) = a + b + c \implies 2017 \,|\, a + b + c; \\ x = -1 \Rightarrow f(-1) = a - b + c \implies 2017 \,|\, a - b + c. \end{aligned}
Then both a+ba + b and aba - b are divisible by 20172017, so are 2a2a and 2b2b. Since 20172017 is odd, all the coefficients are divisible by 20172017.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.