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

• Jul 27th 2008, 03:49 AM
fardeen_gen
Show that n^5 + n^4 + 1 is not prime for n>1
No idea at all!
• Jul 27th 2008, 03:54 AM
Moo
Quote:

Originally Posted by fardeen_gen
No idea at all!

n^5+n^4+1=(x²+x+1)(x^3-x+1)

:D

But I cheated and asked it to Maxima.
• Jul 27th 2008, 06:02 AM
Soroban
Hello, fardeen_gen!

Please don't hide the problem in the heading . . .

Quote:

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)

• Jul 27th 2008, 06:20 AM
fardeen_gen
Thank you. Is expressing the given expression in factors sufficient to prove that it is not a prime?
• Jul 27th 2008, 10:53 PM
Moo
Quote:

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.
• Jul 28th 2008, 02:14 PM
ThePerfectHacker
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$.
• Jul 24th 2013, 08:18 PM
Matan
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)