Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What is $g(x)$ here and what are the common factors? – user117913 Dec 27 '13 at 18:15
up vote 1 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
I know other solutions. Please help me understand the given one. – user117913 Dec 27 '13 at 18:16
The given solution tells you how to get this factorization. – Igor Rivin Dec 27 '13 at 18:20
See edited version. – Yiorgos S. Smyrlis Dec 27 '13 at 18:23
This is the solution that I was looking for. – user117913 Dec 27 '13 at 18:28

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

share|cite|improve this answer

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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.