2
$\begingroup$

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.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory May 19 '17 at 17:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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

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

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

$\endgroup$
4
$\begingroup$

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.

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

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.

$\endgroup$

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