# tough factoring problem

• Dec 28th 2007, 09:51 AM
galactus
tough factoring problem
Here's a somewhat tough factoring problem if anyone would like to have a go.

Factor $x^{10}+x^{5}+1$

Yes, it factors, though it may take some ingenuity.

Some may not find it that bad, but what the heck, have fun if you wish.
• Dec 28th 2007, 11:11 AM
Jhevon
Quote:

Originally Posted by galactus
Here's a somewhat tough factoring problem if anyone would like to have a go.

Factor $x^{10}+x^{5}+1$

Yes, it factors, though it may take some ingenuity.

Some may not find it that bad, but what the heck, have fun if you wish.

$\left( x^5 + \frac 12 + \frac {\sqrt{3}}2~i \right) \left( x^5 + \frac 12 - \frac {\sqrt{3}}2~i \right)$

is that what you meant, galactus?
• Dec 28th 2007, 11:22 AM
ThePerfectHacker
Quote:

Originally Posted by galactus
Here's a somewhat tough factoring problem if anyone would like to have a go.

Factor $x^{10}+x^{5}+1$

Yes, it factors, though it may take some ingenuity.

Some may not find it that bad, but what the heck, have fun if you wish.

You can factor $x^2+x+1 = (x - \zeta)(x-\zeta^2)$ where $\zeta = \cos \frac{2\pi}{3}+i\sin \frac{2\pi}{3}$ this is what Jhevon did.

That means,
$x^{10}+x^5+1 = (x^5 - \zeta)(x^5 - \zeta^2)$

Now we solve $x^5 - \zeta = 0$. Note that $\zeta^{1/5} = \cos \frac{2\pi}{15}+i\sin \frac{2\pi}{15}$, let us call this number $\eta$. Let $\omega = \cos \frac{2\pi}{5}+i\sin \frac{2\pi}{5}$. That means the solution to $x^5 - \zeta=0$ is $\eta,\eta \omega,\eta \omega^2, \eta \omega^3,\eta \omega^4$.

Now we solve $x^5 - \zeta^2 = 0$. The solutions are: $\eta^2, \eta^2 \omega, \eta^2\omega^2,\eta^2 \omega^3, \eta^2 \omega^4$.

That means the full factorization is:
$\prod_{k=1}^4 (x - \eta \omega^k)(x-\eta^2 \omega^k)$.
• Dec 28th 2007, 11:26 AM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
You can factor $x^2+x+1 = (x - \zeta)(x-\zeta^2)$ where $\zeta = \cos \frac{2\pi}{3}+i\sin \frac{2\pi}{3}$ this is what Jhevon did.

yes, that's what i ended up doing in effect. but in getting to that point, i was no where near as elegant. good ol' quadratic formula is what i used

Quote:

That means,
$x^{10}+x^5+1 = (x^5 - \zeta)(x^5 - \zeta^2)$

Now we solve $x^5 - \zeta = 0$. Note that $\zeta^{1/5} = \cos \frac{2\pi}{15}+i\sin \frac{2\pi}{15}$, let us call this number $\eta$. Let $\omega = \cos \frac{2\pi}{5}+i\sin \frac{2\pi}{5}$. That means the solution to $x^5 - \zeta=0$ is $\eta,\eta \omega,\eta \omega^2, \eta \omega^3,\eta \omega^4$.

Now we solve $x^5 - \zeta^2 = 0$. The solutions are: $\eta^2, \eta^2 \omega, \eta^2\omega^2,\eta^2 \omega^3, \eta^2 \omega^4$.

That means the full factorization is:
$\prod_{k=1}^4 (x - \eta \omega^k)(x-\eta^2 \omega^k)$.
wow (Bow)

...my factorization looks stupid and incomplete now :p:D
• Dec 28th 2007, 11:29 AM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
...my factorization looks stupid now :p:D

If you really write out it in terms of numbers then it will get messy, so it is not really elegant. There is a possiblility that if we combine conjuate factors into a quadradic factor the mess might cancel out but I do not have time do to that now.
• Dec 28th 2007, 11:53 AM
galactus
I like the clever approaches, but here is what I was getting at. I failed to elaborate. I apologize.

$x^{10}+x^{5}+1$

Here's what I done. I must admit, I pondered it for a while.

Rewrite as $\frac{(x^{5})^{3}-1}{x^{5}-1}$

$=\frac{x^{15}-1}{x^{5}-1}$

$=\frac{(x^{3})^{5}-1}{(x-1)(x^{4}+x^{3}+x^{2}+x+1)}$

$=\frac{(x^{3}-1)(x^{12}+x^{9}+x^{6}+x^{3}+1)}{(x-1)(x^{4}+x^{3}+x^{2}+x+1)}$

$=\frac{(x^{2}+x+1)(x^{12}+x^{9}+x^{6}+x^{3}+1)}{x^ {4}+x^{3}+x^{2}+x+1}$

Now, if we divide:

$\frac{x^{12}+x^{9}+x^{6}+x^{3}+1}{x^{4}+x^{3}+x^{2 }+x+1}$

results in $x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1$

So, we (as Kriz says) happily have:
$(x^{2}+x+1)(x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1)$

There's more than one way to factorize an expression like this. I just thought it was a cool factoring problem.
• Dec 28th 2007, 01:23 PM
topsquark
Quote:

Originally Posted by galactus
I like the clever approaches, but here is what I was getting at. I failed to elaborate. I apologize.

$x^{10}+x^{5}+1$

Here's what I done. I must admit, I pondered it for a while.

Rewrite as $\frac{(x^{5})^{3}-1}{x^{5}-1}$

$=\frac{x^{15}-1}{x^{5}-1}$

$=\frac{(x^{3})^{5}-1}{(x-1)(x^{4}+x^{3}+x^{2}+x+1)}$

$=\frac{(x^{3}-1)(x^{12}+x^{9}+x^{6}+x^{3}+1)}{(x-1)(x^{4}+x^{3}+x^{2}+x+1)}$

$=\frac{(x^{2}+x+1)(x^{12}+x^{9}+x^{6}+x^{3}+1)}{x^ {4}+x^{3}+x^{2}+x+1}$

Now, if we divide:

$\frac{x^{12}+x^{9}+x^{6}+x^{3}+1}{x^{4}+x^{3}+x^{2 }+x+1}$

results in $x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1$

So, we (as Kriz says) happily have:
$(x^{2}+x+1)(x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1)$

There's more than one way to factorize an expression like this. I just thought it was a cool factoring problem.

Yes, I had originally posted something similar to Jhevon's post, but then recalled that there is a theorem of Gauss'(?) that says that any polynomial with integer coefficients can be expressed as a product of linear and quadratic factors with integer coefficients. (This is part of the statement of the Fundamental Theorem of Algebra.) Since there are no real zeros to this function the 10 zeros must be complex and thus represent 5 quadratic factors.

So this means galactus' 8th degree factor has 4 quadratic factors as well... (Too bad I have never learned any general technique to find them!)

-Dan
• Dec 28th 2007, 01:56 PM
Krizalid
Quote:

Originally Posted by galactus
So, we (as Kriz says) happily have

It's actually "and we happily get" :)

See this problem here.

My "solution" is funny :D
• Dec 29th 2007, 03:04 AM
mr fantastic
Quote:

Originally Posted by topsquark
Yes, I had originally posted something similar to Jhevon's post, but then recalled that there is a theorem of Gauss'(?) that says that any polynomial with integer coefficients can be expressed as a product of linear and quadratic factors with integer coefficients. (This is part of the statement of the Fundamental Theorem of Algebra.) Since there are no real zeros to this function the 10 zeros must be complex and thus represent 5 quadratic factors.

So this means galactus' 8th degree factor has 4 quadratic factors as well... (Too bad I have never learned any general technique to find them!)

-Dan

The stuff in red, I don't think so. An obvious counter-example is x^4 + 1, which factorises as $(x^2 + \sqrt{2}x + 1)(x^2 - \sqrt{2}x + 1)$.
• Dec 29th 2007, 04:40 AM
JaneBennet
This my method. Consider the complex equation

$z^{10}+z^5+1=0$

Multiplying by $z^5-1$,

$z^{15}-1=0$

Hence the solutions to $z^{10}+z^5+1=0$ are all the 15th roots of unity minus the 5th roots of unity, i.e.

$z=\cos{\frac{2k\pi}{15}}\pm\mathrm{i}\sin{\frac{2k \pi}{15}},\ k=1,2,4,5,7$

But two of the solutions (with $k=5$) are

$\cos{\frac{2\pi}{3}}\pm\mathrm{i}\sin{\frac{2\pi}{ 3}}=\frac{-1\pm\mathrm{i}\sqrt{3}}{2}$

These are roots of the equation $x^2+x+1=0$. $\fbox{Hence x^2+x+1 is a factor of x^{10}+x^5+1.}$
• Dec 29th 2007, 07:03 AM
topsquark
Quote:

Originally Posted by mr fantastic
The stuff in red, I don't think so. An obvious counter-example is x^4 + 1, which factorises as $(x^2 + \sqrt{2}x + 1)(x^2 - \sqrt{2}x + 1)$.

Hmmmm... You are right. All those years since I have bothered to apply it had made my brain fuzzy. How about I change that to:
"Every polynomial can be factored (over the real numbers) into a product of linear factors and irreducible quadratic factors."

Apologies and thanks for the catch!

-Dan