<s>[INST] 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?
 [/INST] 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}$$
</s>