$\omega^2+\omega+1$divides a polynomial The question is 
Show that $f(n)=n^5+n^4+1$ is not prime for $n>4$.
The solution is given as
Let $\omega$ be the third root of unity. Then $\omega^2+\omega+1=0$. Since $\omega^5+\omega^4+1=\omega^2+\omega+1$, we see that $\omega^2+\omega+1$ is a *factor of the polynomial. So *$n^2+n+1|n^5+n^4+1$.
Which polynomial are we referring to in the bold typeface above? And how is $n^2+n+1|n^5+n^4+1$ true due to $\omega^5+\omega^4+1=\omega^2+\omega+1$?
 A: This is rather poor phrasing (in the highlighted solution). What it is saying is that that $\omega,$ which is a root of the irreducible polynomial $x^2+x+1$ is also a root of $x^5+x^4+1,$ and so the gcd of the two polynomials is not $1,$ and since the first polynomial is irreducible, it must divide the second. Now, that said, you can verify this without any fanciness by long division.
A: As the 3rd root of identity $\omega=\mathrm{e}^{2\pi i/3}$ satisfies $x^5+x^4+1=0$, then so does its conjugate $\bar\omega=\mathrm{e}^{-2\pi i/3}$, and hence $(x-\omega)(x-\bar\omega)=x^2+x+1$ divides $x^5+x^4+1$. 
Note that
$$
x^5+x^4+1=(x^2+x+1)(x^3-x+1).
$$
A: See that $\omega$ is a root of both $f(x)=x^5+x^4+1$ and $g(x)=x^2+x+1$. Now $g(x)$ has all coefficients real, and it is a polynomial of degree 2. Hence it has two roots and the second root must be the complex conjugate of $\omega$, that is $\omega^2$. Hence $g(x)=(x-\omega)(x-\omega^2)$. Also note that $f(\omega^2)=0$. Hence $f(x)=(x-\omega)(x-\omega^2)h(x)=g(x)h(x)$ for some real polynomial $h(x)$. Now you can easily show by equating coefficients that $h(x)$ has integer coefficients. Now put $x=n$ on both sides. Then since $h(n)$ turns out to be an integer $n^2+n+1|n^5+n^4+1$.
A: Let $$g(n)=n^2+n+1$$ and $$h(n)=n^3-n+1$$.
Clearly $$f(n)=g(n) \cdot h(n)$$
Now $h(1)=1$ and $h'(n) = 3 n^2-1 > 0$ for $n\ge 1$. So, for $n>1$ both $g(n)$ and $h(n)$ are greater than $1$. So
$f(n)$ **is composite for all $n>1$
