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-\phi (n)}$ at all integral arguments are divisible by $n$. (Here $\phi$ 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-\phi (n)}$ and $v\mid k^{\phi (n)}-1$. Having $uv=n$, we can conclude that $n\mid P_n(k)$ as $P_n(k)=k^n-k^{n-\phi (n)}=k^{n-\phi (n)}(k^{\phi (n)}-1)$.

To prove that $u\mid k^{n-\phi (n)}$, it is sufficient to prove for all $i=1,\dots ,l$ that $p_i^{{\alpha }_i}\mid k^{n-\phi (n)}$. It is sufficient to prove that ${\alpha }_i\le n-\phi (n)$, as by the assumption $p_i\mid k$. Inequality ${\alpha }_i\le n-\phi (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^{\phi (n)}-1$, we derive from Euler's theorem that $v\mid k^{\phi (v)}-1$ as $k$ and $v$ are coprime. Also, $u$ and $v$ are coprime, therefore, $\phi (n)=\phi (uv)=\phi (u)\phi (v)$ from which $k^{\phi (v)}-1\mid k^{\phi (n)}-1$. Consequently, $v\mid k^{\phi (n)}-1$.