Monic polynomial divisible by 2018

Let $P(x)$ a monic polynomial (polynomial having leading coefficient one) with integer coefficients such that $P(k)$ is divisible by 2018 for all integer $k$. Find the smallest possible degree of $P$

Solution

Note that $P(x) = x(x+1)(x+1) \dots (x+1008)$ is always divisible by 1009, because one of the factors is always divisible by 1009. It's also even. Therefore $P(x)$ is a polynomial that satisfies the problem requirement, having degree 1009. We shall show that this degree is minimal.

We call a polynomial (not necessarily monic) "good" if it has property that $P(k)$ is divisible by 2018 for all integer $k$.

Suppose $P_n(x)$ is a good monic polynomial having degree $n$, then we apply the following procedure: let $P_{n-1}(x) = P_n(x+1) - P_n(x)$. Then $P_{n-1}$ is a polynomial of degree $n-1$ (because the $x^n$ terms cancel out). Because $P_n$ is good, then $P_{n-1}$ is also good. Furthermore, the leading coefficient of $P_{n-1}$ is $n$, because the only source of $x^{n-1}$ terms is from the expansion of $(x+1)^n$. The other $x^{n-1}$ terms cancel out as well.

We continue this process to obtain $P_{n-2}, P_{n-3},$ and so on. At each step, define $P_m(x) = P_{m+1}(x+1) - P_{m+1}(x)$. We claim the following facts:

1. $P_m$ is good

2. The leading coefficient of $P_m$ is $n(n-1)(n-2) \dots (m+1) = \frac{n!}{m!}$

The two facts can be shown simultaneously using induction. It's obviously true for $m=n$, and as we demonstrated, it's also true for $m=n-1$. If it's true for $m+1$ then it's easy to see that it's true for $m$ as well, using the same argument we showed above.

Thus, at some point, we will arrive at $P_0$ having leading coefficient $n!$. That is, $P_0(x) = n!$ for all $x$, and this must be divisible by 2018 because $P_0$ is good. Therefore $n!$ is divisible by 2018.

What we showed was the necessary condition for a monic polynomial to be good. That is, if it has degree $n$ then $n!$ is divisible by 2018. The smallest possible such $n$ is 1009 because 1009 is prime. But we also showed a sufficient condition, that there exists a polynomial with degree 1009 that's both monic and good. Thus the answer is 1009.