Suppose $p$ is a non-identically 0 polynomial with integer coefficients, such that $p(n)$ is divisible by 2016 for every integer $n$. What is the minimum possible value of the sum of the absolute values of the coefficients of $p$?
Solution. The sum of the absolute values of the coefficients of such a polynomial cannot be zero, for that would mean that all coefficients are zero, but according to the problem's conditions, $p$ is not the identically zero polynomial.

If the sum is 1, then the polynomial must be of the form $p(x)= \pm x^{k}$, where $k$ is a natural number. However, this will not always be divisible by 2016, since for example $p(1)= \pm 1$, which is clearly not divisible by 2016.

In the following, we will show that the sought sum can be 2. For this purpose, consider the polynomial $p(x)=x^{5} \cdot\left(x^{48}-1\right)$. In the following, we will use the Euler-Fermat theorem several times, which states that if $a$ and $n$ are positive integers that are relatively prime, then $n \mid a^{\varphi(n)}-1$, or equivalently, using congruence,

$$
a^{\varphi(n)} \equiv 1 \bmod (n)
$$

where $\varphi(n)$ is the number of positive integers not greater than $n$ that are relatively prime to $n$.

The prime factorization of 2016: $2016=2^{5} \cdot 3^{2} \cdot 7$.

(i) First, we show that $32 \mid p(n)$ for every natural number $n$.

- If $2 \mid n$, then $2^{5} \mid n^{5}$, from which it immediately follows that $2^{5} \mid p(n)$.
- If $n$ is odd, then $(n, 32)=1$, so $n^{\varphi(32)}=n^{16} \equiv 1 \bmod (32)$. From this, it also follows that $n^{48} \equiv 1 \bmod (32)$, meaning that $n^{48}-1$ is divisible by 32.

(ii) Now we prove that $9 \mid p(n)$ for every natural number $n$.

- If $3 \mid n$, then $3^{5} \mid n^{5}$, from which it is clear that $9 \mid p(n)$.
- If $n$ is not divisible by 3, then by the Euler-Fermat theorem, $n^{\varphi(9)}=n^{6} \equiv 1 \bmod (9)$. Consequently, $n^{48} \equiv 1 \bmod (9)$ also holds, meaning that $9 \mid n^{48}-1$, and $p(n)$ is divisible by 9.

(iii) Finally, we show that $7 \mid p(n)$ for every natural number $n$.

- If $7 \mid n$, then $7^{5} \mid n^{5}$, from which it immediately follows that $7 \mid p(n)$.
- If $7 \nmid n$, then by the Euler-Fermat theorem, $n^{\varphi(7)}=n^{6} \equiv 1 \bmod (7)$. Consequently, $n^{48} \equiv 1 \bmod (7)$ also holds, meaning that $7 \mid n^{48}-1$, and $p(n)$ is divisible by 7.

Since 32, 9, and 7 are pairwise relatively prime, from the above, $p(n)$ is also divisible by their product. We have thus found a polynomial $p(n)$ that is divisible by 2016 for every natural number $n$ and the sum of the absolute values of its coefficients is 2.

Remark. Instead of the polynomial $p(x)=x^{5}\left(x^{48}-1\right)$, any other polynomial will do as long as the exponent of $x$ in the first factor is at least 5, and in the second factor, the 48 is replaced by any positive common multiple of 6 and 16.