IMO Team Selection Contest

A single non-zero coefficient is not sufficient for any $n > 1$ as the only simple polynomial functions with a single non-zero coefficient are $P(x) = x^n$ and $P(x) = -x^n$ but in both cases $n \nmid P(1)$. Let us show that the values of the polynomial function $P_n(x) = x^n - x^{n-\varphi(n)}$ at all integral arguments are divisible by $n$. (Here $\varphi$ is the Euler's totient function.) This shows that having 2 non-zero coefficients is sufficient.

Let $k$ be an integer. Let the canonical form of $n$ be $p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ and let us assume without loss of generality that $k$ is divisible by primes $p_1, \dots, p_l$ and is not divisible by primes $p_{l+1}, \dots, p_m$. Define $u = p_1^{\alpha_1} \cdots p_l^{\alpha_l}$ and $v = p_{l+1}^{\alpha_{l+1}} \cdots p_m^{\alpha_m}$. Let us now show that $u \mid k^{n-\varphi(n)}$ and $v \mid k^{\varphi(n)} - 1$. Having $uv = n$, we can conclude that $n \mid P_n(k)$ as $P_n(k) = k^n - k^{n-\varphi(n)} = k^{n-\varphi(n)}(k^{\varphi(n)} - 1)$.

To prove that $u \mid k^{n-\varphi(n)}$, it is sufficient to prove for all $i = 1, \dots, l$ that $p_i^{\alpha_i} \mid k^{n-\varphi(n)}$. It is sufficient to prove that $\alpha_i \le n - \varphi(n)$, as by the assumption $p_i \mid k$. Inequality $\alpha_i \le n - \varphi(n)$ holds as $p_i$, $p_i^2, \dots, p_i^{\alpha_i}$ are $\alpha_i$ positive integers which are not greater than $n$ and not coprime with $n$.

To prove the statement $v \mid k^{\varphi(n)} - 1$, we derive from Euler's theorem that $v \mid k^{\varphi(v)} - 1$ as $k$ and $v$ are coprime. Also, $u$ and $v$ are coprime, therefore, $\varphi(n) = \varphi(uv) = \varphi(u)\varphi(v)$ from which $k^{\varphi(v)} - 1 \mid k^{\varphi(n)} - 1$. Consequently, $v \mid k^{\varphi(n)} - 1$.