Factorise $x^{15}+1$ into two integer polynomials, one of degree 6 and one of degree 9

Question

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.

Answer 1

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$$

Answer 2

(This is equivalent to Fabio Caiazzo's answer, but I'm writing it in more low-brow terms for people who aren't familiar with roots of unity and cyclotomic polynomials.)

Notice that $x^{15}+1$ is divisible by both $x^5+1$ and $x^3+1$, by writing $x^{15}$ as either $(x^5)^3$ or $(x^3)^5$ and using the formula for the sum of odd powers. Each of these two factors is itself divisible by $x+1$, but after factoring that out, they are relatively prime. So you can take the degree-$6$ factor to be $$ \frac{x^5+1}{x+1} \cdot \frac{x^3+1}{x+1}, $$ from which you can find the degree-$9$ factor by long division.