This question was asked as one of the electrical engineering entrance problems in my country, where the term integer polynomial means precisely a polynomial with integer coefficients. The answer given is:
$$\left(x^9+2x^8+x^7-x^6-2x^5-2x^4-x^3+x^2+2x+1\right)\\ \times \left( x^6-2x^5+3x^4-3x^3+3x^2-2x+1\right)$$
My attempt:
My first instinct upon seeing the problem was to consider the factorisation of $x^5+1$ into polynomials of degree two and three, hoping that the degree six and nine polynomials in the question can be recovered by letting $x \mapsto x^3$. Then it occurred to me that I could not do this to get factorisations with nice (integer) coefficients.
One representation I derived was the not-so-good-looking
$$ x^5+1 = \left[ x^3 + \left(\frac{\sqrt{5}+1}{2}\right)x^2 + \left(\frac{\sqrt{5}+1}{2}\right)x + 1 \right]\left[ x^2 – \left(\frac{\sqrt{5}+1}{2}\right)x +1 \right] $$
Which isn't an integer polynomial.
Then I tried to reverse engineer a solution from the answer key provided, to no avail. I noticed that both polynomials in the factorisation are symmetric, in the sense that the coefficients are palindromic: $(1, 2, 1, -1, -2, -2, -1, 1, 2, 1)$ and $(1, -2, 3, -3, 3, -2, 1)$, although I am not sure how this might help solve the problem.
Best Answer
Using the formula $$x^n+1=\prod_{i=1}^{n}\left(x-e^{\frac{\left(2k+1\right)\pi i}{n}}\right)$$ You can split you polynomial into $4$ polynomials of degree $1, 2,4$ and $8$: $$\underbrace{(x + 1)}_{k=7} \underbrace{(x^2 - x + 1)}_{k=2,12} \underbrace{(x^4 - x^3 + x^2 - x + 1)}_{k=1,4,10,13} \underbrace{(x^8 + x^7 - x^5 - x^4 - x^3 + x + 1)}_{k=3,5,6,8,9,11,14,15}$$
the different $k$'s are grouped in such a way that simplifying $\dfrac{2k+1}{15}$, these have the same denominator:
Example
$a_k=\dfrac{2k+1}{15}$ for $k=1,4,10,13\Rightarrow a_k=\dfrac{1}{5},\dfrac{3}{5},\dfrac{7}{5},\dfrac{9}{5}$
So if you want a polynomial of degrees $6$ and $9$
$$p_6(x)=(x^2 - x + 1) (x^4 - x^3 + x^2 - x + 1)$$ $$p_9(x)=(x+1)(x^8 + x^7 - x^5 - x^4 - x^3 + x + 1)$$
So
$$p_6(x)=x^6 - 2 x^5 + 3 x^4 - 3 x^3 + 3 x^2 - 2 x + 1$$ $$p_9(x)=x^9 + 2 x^8 + x^7 - x^6 - 2 x^5 - 2 x^4 - x^3 + x^2 + 2 x + 1$$