No idea at all!

Printable View

- July 27th 2008, 04:49 AMfardeen_genShow that n^5 + n^4 + 1 is not prime for n>1
No idea at all!

- July 27th 2008, 04:54 AMMoo
- July 27th 2008, 07:02 AMSoroban
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.*

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

- July 27th 2008, 07:20 AMfardeen_gen
Thank you. Is expressing the given expression in factors sufficient to prove that it is not a prime?

- July 27th 2008, 11:53 PMMoo
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. - July 28th 2008, 03:14 PMThePerfectHacker
You can note that can be factored using primitive root of unities. Let be a primitive third root of unity then . Now the minimal polynomial for is which is . Thus, a factor of .

- July 24th 2013, 09:18 PMMatanJust for those, who got here from google
**2nd solution:**

We have

n^{5}+ n^{4}+ 1

= n^{5}+ n^{4}+ n^{3}- n^{3}- n^{2}- n +n^{2}+ n + 1

= n^{3}(n^{2}+ n + 1) - n(n^{2}+ n + 1) + (n^{2}+ n + 1)

= (n^{2}+ n + 1)(n^{3}- n + 1)