Solution:

The answer is (E). Let us recall the notable factorization $a^{k}+b^{k}=(a+b)\left(a^{k-1}-a^{k-2} b+a^{k-3} b^{2}-\cdots+b^{k-1}\right)$, valid for $k$ odd. Using this factorization twice (once with $k=3$, once with $k=5$) we have
$$\begin{aligned} x^{16}+x & =x\left(x^{15}+1\right)=x\left(x^{5}+1\right)\left(x^{10}-x^{5}+1\right) \\ & =x(x+1)\left(x^{4}-x^{3}+x^{2}-x+1\right)\left(x^{10}-x^{5}+1\right) . \end{aligned}$$
However, again by the aforementioned factorization, we have that $x^{15}+1$ is also a multiple of $x^{3}+1=(x+1)\left(x^{2}-x+1\right)$. We should therefore expect that the factor $x^{2}-x+1$ can also appear in the decomposition. Indeed, by carrying out polynomial division, we have that
$$x^{10}-x^{5}+1=\left(x^{2}-x+1\right)\left(x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1\right) \text{.}$$
This leads to at least five factors obtainable in the decomposition. Since 5 is the highest answer present among the choices, it is not necessary to also prove that the factors found cannot be further decomposed. A complete proof of this fact is above the level normally required in this competition; it can be obtained by making the substitution $y=-x$ and using the theory of primitive complex roots of unity, or directly by trial based on Gauss's lemma.