# Prove $n^5+n^4+1$ is not a prime

I have to prove that for any $n>1$, the number $n^5+n^4+1$ is not a prime.With induction I have been able to show that it is true for base case $n=2$, since $n>1$.However, I cannot break down the given expression involving fifth and fourth power into simpler terms. Any help?

• What exactly do you mean by "With induction I have been able to show that it is true for base case n=2, since n>1."? – HSN Jan 19 '17 at 16:02
• See Bill Dubuque's answer to another recent question. – Jyrki Lahtonen Jan 19 '17 at 16:10
• @HSN: since n>1, i took the base case as n=2 and found that the given expression is equal to 49 which is certainly not a prime. Hence, the proposition is true for n=2. – deepa kapoor Jan 19 '17 at 16:16
• @Jyrki Lahtonen : thanks for that link – deepa kapoor Jan 19 '17 at 16:20
• As Jyrki mentioned, if follows from the Lemma below, whose simple proof is in this answer $$x^{2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ \ \ {\rm if}\ \ \ \{A,B,C\}\equiv \{2,1,0\}\pmod{\!3}$$ – Bill Dubuque Jan 19 '17 at 16:34

$n^5 + n^4 + 1 = n^5 + n^4 + n^3 – n^3 – n^2 − n + n^2 + n + 1$
$\implies$$n^3(n^2 + n + 1) − n(n^2 + n + 1) + (n^2 + n + 1) = (n^2 + n + 1)(n^3 − n + 1) Hence, for n>1, n^5 + n^4 + 1 is not a prime number. • You might want to add that neither n^2+n+1, nor n^3-n+1 can be 1 for n>1. Else it could still be a prime number. – HSN Jan 19 '17 at 16:04 • Thanks I have made an edit , even though it is mentioned in the question that n>1 – naveen dankal Jan 19 '17 at 16:47 n^5+n^4+1=(n^3-n+1)(n^2+n+1) • I think you answer would benefit from explaing why and how you arrived to this factorisation. – TZakrevskiy Jan 19 '17 at 16:05$$n^5+n^4+1=n^5-n^2+n^4+n^2+1=n^2(n-1)(n^2+n+1)+(n^2+n+1)(n^2-n+1)==(n^2+n+1)(n^3-n^2+n^2-n+1)=(n^2+n+1)(n^3-n+1)$$I think, the best way is the following:$$n^5+n^4+1=n^5+n^4+n^3-(n^3-1)=(n^2+n+1)(n^3-n+1)$\$