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

This question already has an answer here:

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.

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 19 '17 at 17:51

• HINT: Divisible by $$n^2+n+1$$ – lab bhattacharjee May 18 '17 at 8:38
• @labbhattacharjee Thanks. – user333900 May 18 '17 at 8:40
• Observe that $$n^2+n+1$$ actually divides $$n^{3a+2}+n^{3b+1}+1$$ – lab bhattacharjee May 18 '17 at 8:59

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}

• (+1) I really like when somebody helps the OP goes forward with his idea. – Arnaldo May 18 '17 at 23:13
• @Arnaldo Thanks. This is one case where the OP helped their cause by providing some context. – dxiv May 18 '17 at 23:18

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

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.

• This is explained at length in the post linked in my answer. – Bill Dubuque May 19 '17 at 17:50

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.