12. Francesco wants to write the polynomial $x^{16}+x$ as a product of multiple polynomials with integer coefficients, each of degree at least 1. What is the maximum number of factors he can obtain?
(A) 1
(B) 2
(C) 3
(D) 4
(E) 5.

## Numerical Answer Problems - 5 points
12. The answer is (E). Let's 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 odd $k$. 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, by the aforementioned factorization, $x^{15}+1$ is also a multiple of $x^{3}+1=(x+1)\left(x^{2}-x+1\right)$. Therefore, we should expect that the factor $x^{2}-x+1$ can also appear in the factorization. Indeed, performing 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 brings the number of factors obtained in the factorization to at least five. Since 5 is the highest answer among the choices, it is not necessary to prove that the factors found are not further decomposable. A complete proof of this fact is beyond 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.