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?
Best Answer
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$.