# Factoring $a^{10}+a^5+1$

I'm very interested to know how I can factorise $a^{10} +a^5 +1$ in two factors with integer coefficients. I've tried a lot but I don't have any idea how do that.

-
You can immediately get the answer using quickmath.com/webMathematica3/quickmath/algebra/factor/… – Shai Covo Mar 2 '11 at 2:13
Does this look like a geometric series? Base=1, ratio=$a^5$. – Ross Millikan Mar 2 '11 at 6:05

Another hint: can you factor $a^{15}-1$? In more than one way?

-
A big winner. I upvoted all the answers to this, as they are all helpful, but if I could give more votes to one, this would be it. – Ross Millikan Mar 2 '11 at 6:00
Ross, thanks for the compliment! – Michael Lugo Mar 2 '11 at 21:57
Sorry, but I can not realize this hint. Why that? sorry – tom Mar 2 '11 at 23:19
tom: because polynomials have unique factorization, if you can find multiple distinct factorizations of $a^{15}-1$, you're guaranteed to be able to break them down further into a 'common' factorization. Now, your polynomial in $a$ is one factor in an obvious factorization of $a^{15}-1$; there's another obvious factorization, and comparing the two should prove fruitful. – Steven Stadnicki Mar 23 '11 at 18:27
See my answer for the underlying divisibility theory. – Bill Dubuque Mar 24 '11 at 3:24

A nice way to proceed is to exploit the fact that the polynomial sequence $\rm\ f_n = (x^n-1)/(x-1)\$ is a strong divisibility sequence, i.e. $\rm\: (f_m,f_n)\ =\ f_{\:(m,n)}\:,$ where $\rm\:(u,v)\:$ denotes $\rm\:gcd(u,v)\:.\:$ So, for example, $\rm\ (f_3,f_5) = f_{\:(3,5)} = f_1 = 1\:,\:$ and $\rm\ f_3\:|\:f_{15}\$ via $\rm\ (f_3,f_{15}) = f_{\:(3,15)} = f_3\:.\:$ Combining this with Euclid's Lemma quickly yields the sought factor, namely

$\rm\quad\quad (f_3,f_5) = 1,\ \ f_3,f_5\:|\:f_{15}\ \ \Rightarrow\ \ f_3\:f_5\:|\:f_{15}\ \ \Rightarrow\ \ f_3\:|\:f_{15}/f_5\:,\$ i.e. $\rm\ \ x^2+x+1\ |\ x^{10}+x^5+1\$

Note that the above proof shows $\rm\ (a,b) = 1\ \Rightarrow\ f_a\ |\ f_{a\:b}/f_b\$ for any strong divisibility sequence $\rm\:f_n\:.\:$ For example, for the fibonacci numbers follows $\rm\ f_5\ |\ f_{20}/f_4\$ i.e. $\rm\ 5\ |\ 6765/3\: =\: 2255\:.$

More generally, using these properties and a little number theory and combinatorics (inclusion-exclusion) one easily derives the basic factorization properties of cyclotomic polynomials.

The proof of the basic property $\rm\: (f_m,f_n)\: =\: f_{\:(m,n)}\:$ is very simple - essentially the same as the proof of the Bezout identity for integers - see my post here. $\:$ This allows one to view the polynomial Bezout identity as a q-analog of the integer Bezout identity. For example, let's compare the Bezout identity for the gcd $\rm\ 3 = (15,21)\$ in polynomial and integer form:

$\rm\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \: \frac{x^3-1}{x-1}\ =\ (x^{15} + x^9 + 1)\ \frac{x^{15}-1}{x-1}\ -\ (x^9+x^3)\ \frac{x^{21}-1}{x-1}$

for $\rm\ x = 1\$ specializes to $\ \ 3\ =\ (3)\ 15\ -\ (2)\ 21\:.\$ It is well-worth mastering these binomial divisibility properties since they occur quite frequently in number theoretical applications and, moreover, they provide excellent motivation for the more general study of divisibility theory. $\quad\ \$ For an introduction see Borovich and Shafarevich: Number Theory.

-

If you really have no other way: Substitute x for a^5, so you get x^2+x+1.

Then use some quadratic formula action, then use some factoring action on those binomials, then just try all possible products of the factors you get until something nice comes out.

I could see this being not so nice a solution though.

-
Why? Substituting for a^5 is the obvious thing that jumped to mind for me. – user7530 Mar 2 '11 at 8:50

Hint: It clearly does not have a linear factor since $\pm1$ is not a root. Try a quadratic factor $a^2+u a+v$, for some integers $u$ and $v$.

-