# On factorizing and solving the polynomial: $x^{101} – 3x^{100} + 2x^{99} + x^{98} – 3x^{97} + 2x^{96} + \cdots + x^2 – 3x + 2 = 0$

The actual problem is to find the product of all the real roots of this equation,I am stuck with his factorization:

$$x^{101} – 3x^{100} + 2x^{99} + x^{98} – 3x^{97} + 2x^{96} + \cdots + x^2 – 3x + 2 = 0$$

By just guessing I noticed that $(x^2 – 3x + 2)$ is one factor and then dividing that whole thing we get $(x^{99}+x^{96}+x^{93} + \cdots + 1)$ as the other factor , but I really don't know how to solve in those where wild guessing won't work! Do we have any trick for factorizing this kind of big polynomial?

Also I am not sure how to find the roots of $(x^{99}+x^{96}+x^{93} + \cdots + 1)=0$,so any help in this regard will be appreciated.

-
$x^{99} + x^{96} + ...$ is a finite geometric series. –  Qiaochu Yuan Sep 7 '11 at 20:26
At least you could write it as $(x^2 - 3x + 2)(x^{102} - 1)/(x^3 - 1)$, making it a bit of a cleaner expression. –  TMM Sep 7 '11 at 20:27
It is not correct to characterize your finding of the factor $x^2-3x+2$ as "just guessing," let alone "wild guessing!" The decision that $x^2-3x+2$ might be a factor was surely motivated by the obvious structure. There are techniques, some quite sophisticated, for factoring polynomials of large degree that are structureless. These are embedded in factoring software. For factorization of polynomials of large degree "by hand," you will only meet highly structured polynomials. –  André Nicolas Sep 7 '11 at 21:13
@André Nicolas:I don't really knew about the structure before today I just guessed it this is a quantitative aptitude problem and I am suggested to make this kind of wild guesses by my instructor ;) it also seems obvious as $\cdots + x^2 – 3x + 2$ are the last terms,got lucky I suppose!However I guess I can somehow see the structure now,would you like to give me some more theory/problems to strengthen my newly obtained skills? –  Quixotic Sep 7 '11 at 21:24
A good idea when factoring a polynomial (especially one that comes from a homework problem) is to look for obvious roots. For example, it's very easy to evaluate the polynomial at $0$ (constant term), $1$ (sum of coefficients) and $-1$ (alternating sum of coefficients), trying other value can be done with Horner's scheme. Applying this, you could find that $-1$, $1$ and $2$ are roots (finding $2$ is admittedly the hardest, but you actually found it). Once you clear them out, you end with a polynomial with no real root (as is explained in Zev's answer below). –  Joel Cohen Sep 7 '11 at 21:48

Note that $$t^{34}-1=(t^{33}+t^{31}+\cdots+t+1)(t-1)$$ and so, substituting $t=x^3$, we get $$x^{102}-1=(x^{99}+x^{96}+\cdots+x^3+1)(x^3-1)$$ So any real root of $x^{99}+x^{96}+\cdots+x^3+1$ will be a real root of $x^{102}-1$ (and those should be easy to find). But note that, for example, $1$ is a real root of $x^{102}-1$, but is not a root of $x^{99}+x^{96}+\cdots+x^3+1$, since $34=1+1+\cdots+1\neq0$. So, once you find the real roots of $x^{102}-1$ and determine which of them is in fact a root of $x^{99}+x^{96}+\cdots+x^3+1$, you can combine with the real roots of $x^2-3x+2=(x-1)(x-2)$ to get the answer.

To factorize $x^{99}+x^{96}+\cdots+x^3+1$ into irreducibles over $\mathbb{Z}$ (which, it turns out, is equivalent to factoring into irreducibles over $\mathbb{Q}$ in this case), we use the fact that $$x^{99}+x^{96}+\cdots+x^3+1=\frac{x^{102}-1}{x^3-1}$$ combined with the fact that $$x^{102}-1=\prod_{d\mid 102}\Phi_d(x)=\Phi_{102}(x)\Phi_{51}(x)\Phi_{34}(x)\Phi_{17}(x)\Phi_6(x)\Phi_3(x)\Phi_2(x)\Phi_1(x)$$ where $\Phi_d(x)$ is the $d$th cyclotomic polynomial. The cyclotomic polynomials are all irreducible over $\mathbb{Q}$. Any irreducible polynomial in $\mathbb{R}[x]$, though, is either a linear $x-a$ for $a\in\mathbb{R}$, or a quadratic $x^2+ax+b$ for which $a^2-4b<0$. The factorization into irreducibles over $\mathbb{R}$ is just $(x-1)$, $(x+1)$, and then a bunch of quadratics $$x^2-(\zeta_{102}^k+\overline{\zeta_{102}}^k)x+1=(x-\zeta_{102}^k)(x-\overline{\zeta_{102}}^k)$$ where $\zeta_{102}$ is a primitive $102$th root of unity and $0<k<51$.

Of course, the factorization into irreducibles over $\mathbb{C}$ is just $$(x-1)(x-\zeta_{102})(x-\zeta_{102}^2)\cdots(x-\zeta_{102}^{50})(x+1)(x-\zeta_{102}^{52})\cdots(x-\zeta_{102}^{101})$$ Wolfram Alpha has a nice printout with the conjugate pairs, it may be helpful.

-
+1!Thanks,that's a good answer(although things seems more easy to me if I just use the summation of G.P series for the part $(x^{99}+x^{96}+\cdots+x^3+1)=\frac{(x^{102} - 1)}{(x^3 - 1)}$).However,this only answers the second part of my question,for finding the factors could you think of anything except guessing? –  Quixotic Sep 7 '11 at 20:42
It factors into product of cyclotomic polynomials. See en.wikipedia.org/wiki/Cyclotomic_polynomial –  Soarer Sep 7 '11 at 20:48
@FoolForMath: I'll make an edit explaining the factorization. –  Zev Chonoles Sep 7 '11 at 20:48
@Zev Chonoles:Alright! :) –  Quixotic Sep 7 '11 at 20:51
@FoolForMath Are you asked to factor it? What I like about this problem as stated is that you don't have to do that. –  Dylan Moreland Sep 7 '11 at 21:34

In regard to the first part of your question ("wild guessing"), the point was to note that the polynomial can be expressed as the sum of three polynomials, grouping same coefficients:

$$P(x)= x^{101} – 3x^{100} + 2x^{99} + x^{98} – 3x^{97} + 2x^{96} + \cdots + x^2 – 3x + 2 = A(x)+B(x)+C(x)$$

with

$$\begin{eqnarray} A(x) &= x^{101} + x^{98} + \cdots + x^2 &= x^2 (x^{99} + x^{96} + \cdots + 1) \\ B(x) &= - 3 x^{100} -3 x^{97} - \cdots -3 x &= - 3 x (x^{99} + x^{96} + \cdots + 1)\\ C(x) &= 2 x^{99} + 2 x^{96} + \cdots + 2 &= 2 (x^{99} + x^{96} + \cdots + 1) \\ \end{eqnarray}$$

so $$P(x) = (x^2 - 3x +2) (x^{99} + x^{96} + \cdots + 1)$$

and applying the geometric finite sum formula:

$$P(x)=(x^2 - 3x +2) ({(x^{3})}^{33} + {(x^{3})}^{32} + \cdots + 1) = (x^2 - 3x +2) \frac{x^{102}-1}{x^3-1}$$

As Andre notes in the comments, your "guessing" was dictated by the very particular structure of the polynomial, you can't hope for some general guessing recipe...

-