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.

Solution 1:

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

Six years later, for the record, let's spell out what I meant by this. What I had intended was to observe

$$a^{15}-1 = (a^3)^5 - 1 = (a^3-1)(a^{12} + a^9 + a^6 + a^3 + 1) = (a-1)(a^2+a+1)(a^{12} + a^9 + a^6 + a^3 + 1)$$

and also

$$a^{15}-1 = (a^5)^3 - 1 = (a^5-1)(a^{10} + a^5 + 1) = (a-1) (a^4+a^3+a^2+a+1) (a^{10}+a^5+1)$$

Thus we have

$$(a^2+a+1) (a^{12}+a^9 + a^6 + a^3 + 1) = (a^4 + a^3 + a^2 + a + 1)(a^{10} + a^5 + 1)$$

and so

$$a^{10} + a^5 + 1 = (a^2 + a + 1) \times {a^{12} + a^9 + a^6 + a^3 + 1 \over a^4 + a^3 + a^2 + a + 1}$$

Now, since $a^2 + a + 1 = (a^3-1)/(a-1)$, the roots of $a^2 + a + 1$ are just the two complex cube roots of unity; it's easy to check that $a^{10} + a^5 + 1$ has those same roots. So that quotient is in fact a polynomial. We can find out what polynomial it is by long division, and we get the answer:

$$a^{10} + a^5 + 1 = (a^2 + a + 1) (a^8 - a^7 + a^5 - a^4 + a^3 - a + 1).$$

Solution 2:

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.

Solution 3:

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.

Solution 4:

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$.