No idea at all!

Printable View

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

- Jul 27th 2008, 03:54 AMMoo
- Jul 27th 2008, 06: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)**

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

- Jul 27th 2008, 10: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. - Jul 28th 2008, 02:14 PMThePerfectHacker
You can note that $\displaystyle x^5+x^4+1$ can be factored using primitive root of unities. Let $\displaystyle \zeta$ be a primitive third root of unity then $\displaystyle \zeta^5+\zeta^4+1 = \zeta^2 + \zeta + 1 = 0$. Now the minimal polynomial for $\displaystyle \zeta$ is $\displaystyle \Phi_3(x) $ which is $\displaystyle x^2+x+1$. Thus, $\displaystyle x^2+x+1$ a factor of $\displaystyle x^5+x^4+1$.

- Jul 24th 2013, 08: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)