# Math Help - Show that n^5 + n^4 + 1 is not prime for n>1

1. ## Show that n^5 + n^4 + 1 is not prime for n>1

No idea at all!

2. Originally Posted by fardeen_gen
No idea at all!
n^5+n^4+1=(x²+x+1)(x^3-x+1)

But I cheated and asked it to Maxima.

3. Hello, fardeen_gen!

Show that n^5 + n^4 + 1 is not prime for n > 1.
Brilliant move, moo!

I found a way to factor it. .(It helped that I already knew the factors!)

Let: .P .= .n^5 + n^4 + 1

Multiply by (n - 1):

. . (n - 1)P . = . (n - 1)(n^5 + n^4 + 1)

- - . . . . . . .= . n^6 - n^4 + n - 1

- - . . . . . . .= . (n^6 - 1) - (n^4 - n)

- - . . . . . . .= . (n³ - 1)(n³ + 1) - n(n³ - 1)

- - . . . . . . .= . (n³ - 1)(n³ - n + 1)

. . (n - 1)P . = . (n - 1)(n² + n + 1)(n³ - n + 1)

Divide by (n - 1): . P . = . (n² + n + 1)(n³ - n + 1)

4. Thank you. Is expressing the given expression in factors sufficient to prove that it is not a prime?

5. Originally Posted by fardeen_gen
Thank you. Is expressing the given expression in factors sufficient to prove that it is not a prime?
Not really, because it still can be 1 multiplied by a prime number.

But you can see that n²+n+1 > 1 for any n>1.
For any n>1, n^3>n, and than n^3-n>0 --> n^3-n+1>1.

So both factors are strictly > 1, which proves that it's a product of 2 numbers > 1, thus not prime.

6. You can note that $x^5+x^4+1$ can be factored using primitive root of unities. Let $\zeta$ be a primitive third root of unity then $\zeta^5+\zeta^4+1 = \zeta^2 + \zeta + 1 = 0$. Now the minimal polynomial for $\zeta$ is $\Phi_3(x)$ which is $x^2+x+1$. Thus, $x^2+x+1$ a factor of $x^5+x^4+1$.

7. ## Just for those, who got here from google

2nd solution:

We have
n5 + n4 + 1

= n5 + n4 + n3 - n3 - n2 - n +n2 + n + 1

= n3(n2 + n + 1) - n(n2 + n + 1) + (n2 + n + 1)

= (n2 + n + 1)(n3 - n + 1)