14th Turkish Mathematical Olympiad

Using the fact that $$Q(x{)}^{7^m}\equiv Q(x^{7^m})(\mathrm{mod}7)$$ for all polynomials $Q(x)$ with integer coefficients and for all positive integers $m$, we see that the integers $n=7^k$ and $n=7^k+7^l$ with $0\le k\le l$ satisfy the condition of the problem.

Now we will show that if $n$ is not of this form, then it does not satisfy the condition of the problem. Without loss of generality we may assume that $n$ is not divisible by $7$.

As $n>2$, the coefficient of $x^3$ in $P_n(x)$ is $n(n-1)$. If $7|n(n-1)$, then $7|n-1$. Let $a\ge 1$ and $b\ge 2$ be integers such that $7\nmid b$ and $n=1+7^{a}b$. Then we have

the following set of congruences modulo $7$: $$\begin{gathered} (x^2+x+1{)}^n\equiv (x^2+x+1)(x^2+x+1{)}^{7^a}\equiv (x^2+x+1)(x^{2\cdot 7^a}+x^{7^a}+1{)}^b \\ \equiv 1+x+x^2+b{x}^{7^a}+b{x}^{7^a+1}+b{x}^{7^a+2} \\ +\text{(terms of order }2\cdot 7^a\text{ or larger)} \end{gathered}$$ $$(x+1{)}^n\equiv 1+x+b{x}^{7^a}+b{x}^{7^a+1}+\text{(terms of order }2\cdot 7^a\text{ or larger)}$$ $$(x^2+1{)}^n\equiv 1+x^2+\text{(terms of order }2\cdot 7^a\text{ or larger)}$$ $$(x^2+x{)}^n\equiv \text{(sum of terms of order }2\cdot 7^a\text{ or larger)}$$ (In the last congruence we used the fact that $b\ge 2$.) Putting these together we get $$P_n(x)\equiv b{x}^{7^a+2}+\text{(terms of order }2\cdot 7^a\text{ or larger)}(\mathrm{mod}7).$$ Since $b$ is not divisible by $7$, the coefficient of $x^{7^a+2}$ in $P_n(x)$ is not divisible by $7$.