Putnam 2016, Problem A-1

Find the smallest positive integer \( j \) such that for every polynomial \( p(x) \) with integer coefficients and for every integer \( k \), the integer
\[
p^{(j)}(k) = \left. \frac{d^j}{dx^j} p(x) \right|_{x=k}
\]
(the \( j \)-th derivative of \( p(x) \) at \( k \)) is divisible by 2016.

Solution:
The answer is $j = 8$. First suppose that $j$ satisfies the given condition. For $p(x) = x^j$, we have $p^{(j)}(x) = j!$ and thus $j!$ is divisible by 2016. Since 2016 is divisible by $2^5$ and 7! is not, it follows that $j \geq 8$. Conversely, we claim that $j = 8$ works. Indeed, let $p(x) = \sum_{m=0}^n a_m x^m$ be a polynomial with integer coefficients; then if $k$ is any integer,

$$p^{(8)}(k) = \sum_{m=8}^n m(m-1)\cdots(m-7)a_m k^{m-8} = \sum_{m=8}^n \binom{m}{8} 8! a_m k^{m-8}$$

is divisible by $8! = 20 \cdot 2016$, and so $p^{(8)}(k)$ is divisible by 2016.

**Remark:** By the same reasoning, if one replaces 2016 in the problem by a general integer $N$, then the minimum value of $j$ is the smallest one for which $N$ divides $j!$. This can be deduced from Pólya's observation that the set of integer-valued polynomials is the free $\mathbb{Z}$-module generated by the binomial polynomials $\binom{x}{n}$ for $n = 0, 1, \ldots$. That statement can be extended to polynomials evaluated on a subset of a Dedekind domain using Bhargava's method of $P$-orderings; we do not know if this generalization can be adapted to the analogue of this problem, where one considers polynomials whose $j$-th derivatives take integral values on a prescribed subset.