How to think of factorising $x^7+x^2+1$ to $(x^2+x+1)(x(x-1)(x^3+1)+1)$ (Thales 2016) I was just doing the following question:
Find a prime number which divides the number $A=14^7+14^2+1$.
I solved it by finding the result which is $A=105413504+196+1=105413701$ and then trying out all prime numbers till I found that 211 divides it. However, obviously this is extremely tedious. I hence looked at the solution which says that $x^7+x^2+1=(x^2+x+1)(x(x-1)(x^3+1)+1)$ and from here by saying that $x=14$ we get the solution. However I can't seem to think of how to intuitively turn  $x^7+x^2+1$ into $(x^2+x+1)(x(x-1)(x^3+1)+1)$. I realize that from the question it is obvious to go looking for factors of A and hence trying to factorize $14^7+14^2+1$, but I can't work out how to go about factorizing it, what are the steps which you need to take in order to factorize a given polynomial. Could you please explain to me how to go about factorizing such an expression and how to intuitively think of each step?
 A: You can "see" that $\omega = \exp \left( \frac{2i\pi}{3}\right)$ and $\omega^2= \exp \left( \frac{-2i\pi}{3}\right)$ are roots of $x^7+x^2+1$, therefore $x^7+x^2+1$ factorizes by $x^2+x+1$.
A: By the factor theorem, $x^7+x^2+1$ has no rational roots and no linear factors over $\Bbb Z$, so we look for quadratic factors. To avoid non-integer coefficients, the only such factors are of the form $x^2+ax+1$. The case $a=1$ looks especially promising because, modulo $x^2+x+1$,$$x^3+1\implies x^7=x\implies x^7+x^2+1=0.$$This is essentially the reasoning in @TheSilverDoe's answer, but saves us having to work with explicit roots. As for finding the quotient, note$$\begin{align}x^7+x^2+1&=x(x^6-1)+x^2+x+1\\&=x(x^3-1)(x^3+1)+x^2+x+1\\&=(x^2+x+1)(x(x^3-1)(x+1)+1).\end{align}$$
A: Another way:
$$x^7+x^2+1=x^7-x^4+x^4+x^2+1=(x^2+x+1)(x^4(x-1)+x^2-x+1)=$$
$$=(x^2+x+1)(x^5-x^4+x^2-x+1).$$
A: Hint: $x^2+x+1$ always divides $x^a+x^b+x^c$ if $\{a, b, c) \equiv \{0, 1, 2\} \mod 3$.  Hence it is easy to note $14^7+14^2+1 \equiv 0 \pmod {14^2+14+1}$, and all that remains is checking primality of $211$.
In case you wish to find the other factor(s), in this case, it may be simpler to consider dividing by $x^3-1$, like so:
$$x^7+x^2+1 = x^4(x^3-1) + x(x^3-1)+(x^2+x+1)$$
$$\implies \frac{x^7+x^2+1}{x^2+x+1} = x^4(x-1)+x(x-1)+1=(x-1)(x^4+x)+1$$
