Prove that $n^5+n^4+1$ is composite for $n>1.$ [duplicate]

Question

Prove that $f(n)=n^5+n^4+1$ is composite for $n>1, n\in\mathbb{N}$.

This problem appeared on a local mathematics competition, however it looks like there is no simple method to solve it. I tried multiplying it by $n+1$ or $n-1$ and then tried factorizing it, but it was too tough for me.

Any help will be appreciated.

Answer 1

Building upon OP's idea:

I tried multiplying it by $n+1$ or $n-1$ and then tried factorising it

$$ \begin{align} (n-1)(n^5+n^4+1) = \color{red}{n^6} \color{blue}{- n^4 + n} \color{red}{- 1} &= \color{red}{(n^3-1)(n^3+1)} \color{blue}{-n(n^3-1)} \\ &= (n^3-1)(n^3-n+1) \\ &= (n-1)(n^2+n+1)(n^3-n+1) \end{align} $$

Answer 2

$$n^5+n^4+1 = n^5 - n^2 + n^4 + n^2 + 1 = n^2(n^3-1) + (n^2+1)^2 - n^2 = n^2(n-1)(n^2+n+1) + (n^2-n+1)(n^2+n+1) = (n^3-n+1)(n^2+n+1)$$

Answer 3

If $\omega$ is a (complex) root of $x^2+x+1$, then $\omega^3 - 1 = (\omega-1)(\omega^2+\omega+1) = (\omega-1)\cdot 0 = 0$, and hence $\omega^3 = 1$.

Observe then that $\omega^5 = \omega^3 \cdot \omega^2 = 1 \cdot \omega^2 = \omega^2$ and $\omega^4 = \omega^3 \cdot \omega^1 = 1 \cdot \omega = \omega$, so that $\omega^5+\omega^4 +1 = \omega^2 +\omega + 1 = 0$, hence $\omega$ is a root of $x^5+x^4+1$. Hence both roots of $x^2+x+1$ are roots of $x^5+x^4+1$ and thus $(x^2 + x + 1) \mid (x^5+x^4+1)$.

Note that by a similar argument we can show that $x^2+x+1$ is a factor of $x^8+x^7 + 1$ or even of $x^{101}+x^4+1$. All that matters is that the exponents give all the different residues modulo $3$.

This problem appears as E$13$ in the Number Theory Chapter of Arthur Engel's Problem Solving Strategies.

Answer 4

Hint $\ \ x^{2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ $ if $ \ \{A,B,C\}\equiv \{2,1,0\}\pmod{\!3}\ $ because

$\ \ {\rm mod}\,\ x^2\!+\!x\!+\!1\!:\,\ x^3\equiv 1\,\Rightarrow\, x^N\!\equiv x^{N\!\pmod{\! 3}}$

Remark $\ $ See here for generalizations of this frequently useful test for cyclotomic factors.