$\omega^2+\omega+1$divides a polynomial

Question

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$?

Answer 1

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.

Answer 2

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). $$

Answer 3

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$.

Answer 4

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$