Factor $x^{35}+x^{19}+x^{17}-x^2+1$

Question

I tried to factor $x^{35}+x^{19}+x^{17}-x^2+1$ and I can see that $\omega$ and $\omega^2$ are two conjugate roots of $x^{35}+x^{19}+x^{17}-x^2+1$. So I divide it by $x^2+x+1$ and the factorization comes to the following

$$(x^2+x+1)(x^{33}-x^{32}+x^{30}-x^{29}+x^{27}-x^{26}+x^{24}-x^{23}+x^{21}-x^{20}+x^{18}-x^{16}+2x^{15}-x^{14}-x^{13}+2x^{12}-x^{11}-x^{10}+2x^{9}-x^{8}-x^{7}+2x^6-x^5-x^4+2x^3-x^2-x+1)$$

I couldn't go further. My question is is it end here or there is a simple way to do further?

Answer 1

I think if we simply add and then subtract $x^{18}$ and x this factorization becomes easier. $x^{35} + x^{19} + x^{17} - x^{2} +1 = x^{35}- x^{18}+ x^{17}+ x^{19}- x^{2}+x+ x^{18}- x+ 1$ = $x^{17}(x^{18}-x+1)+ x(x^{18}-x +1)+(x^{18}- x +1)$= $(x^{18}-x+1)(x^{17}+x+1)$. Now it is easy to see that omega is a root of $x^{17}+x+1$ which means $x^{2}+x+1$ is a factor of $x^{17}+x+1$. Now applying vanishing method on $x^{17}+x+1$ we easily get $x^{17}+x+1$ = $(x^{2}+x+1)(x^{15}-x^{14}+x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{5}+x^{3}-x^{2}+1$).So our required solution is $x^{35}+x^{19}+x^{17}-x^{2}+1=(x^{18}-x+1)(x^{2}+x+1)(x^{15}-x^{14}+x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{5}+x^{3}-x^{2}+1)$

Answer 2

Can one find the factors by hand? Well, perhaps with a bit of guessing.

---

In the big factor $$\begin{align}p_{33}(x)&=x^{33}-x^{32}\\&+x^{30}-x^{29}\\&+x^{27}-x^{26}\\&+x^{24}-x^{23}\\&+x^{21}-x^{20}\\&+x^{18}\\&-x^{16}+2x^{15}-x^{14}\\&-x^{13}+2x^{12}-x^{11}\\&-x^{10}+2x^{9}-x^{8}\\&-x^{7}+2x^6-x^5\\&-x^4+2x^3-x^2\\&-x+1,\end{align}$$ you may notice a pattern that is almost perfect, namely we almost always can group the monomials as $x^{n+1}-x^n$ (or, in particular in lower degrees, as $x^{n+2}-2x^{n+1}+x^n=(x^{n+2}-x^{n+1})-(x^{n+1}-x^n)$. Only $x^{18}$ does not fit into this. And if we want to insist on the $x^{n+2}-2x^{n+1}+x^n$ pattern for all low degrees, then also $-x+1$ dose not fit any more. Thus $$p_{33}(x)=(x^{18}-x+1)+ (x-1)\cdot x^2\cdot p_{30}(x)$$ for some degree $30$ polynomial $p_{30}$, which happens to be nice in that it suspiciously only has coefficients $\in\{-1,0,1\}$. Of course, such an additive composition is usually of no help to finding a factorization. Out of despair, we check if $p_{30}$ is a multiple of the first dummand $x^{18}-x+1$ and by chance succeed: $$\begin{align}p_{30}(x)&=x^{30} + x^{27} + x^{24} + x^{21} + x^{18} - x^{13} + x^{12} - x^{10} + x^9 - x^7 + x^6 - x^4 + x^3 - x + 1\\ &=(x^{18}-x+1)(x^{12} + x^9 + x^6 + x^3 + 1) \end{align}$$ and that last factor is easily recognized as $\frac{x^{15}-1}{x^3-1}$, which might be considered motivational. However, $p_{30}$ is not what we wanted to factor. Nevertheless, our pipe-dream made us arrive at $$p_{33}(x)=(x^{18}-x+1)\cdot p_{15}(x)$$ with $$\begin{align}p_{15}(x)&=1+(x-1)x^2\frac{x^{15}-1}{x^3-1}\\&=1+x^2\frac{x^{15}-1}{x^2+x+1} \\&=x^{15} - x^{14} + x^{12} - x^{11} + x^9 - x^8 + x^6 - x^5 + x^3 - x^2 + 1.\end{align}$$