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?
You can &quot;see&quot; 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$.
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$$