factorization of primitive polynomial

As an application of the parent entry (http://planetmath.org/EliminationOfUnknown) we take the factorization of a primitive polynomial of $\mathbb{Z}[x]$ into primitive (http://planetmath.org/PrimitivePolynomial) prime factors.  We shall see that the procedure may be done by performing a finite number of tests.

Let

$$a(x)=:a_n{x}^n+a_{n-1}{x}^{n-1}+\mathrm{\dots }+a_0$$

be a primitive polynomial in $\mathbb{Z}[x]$.

By the rational root theorem and the factor theorem, one finds all first-degree prime factors $x-a$ and thus all primitive prime factors of the polynomial $a(x)$.

If $a(x)$ has a primitive quadratic factor, then it has also a factor

$x^2+px+q$(1)

where $p$ and $q$ are rationals (and conversely).  For settling the existence of such a factor we treat $p$ and $q$ as unknowns and perform the long division

$$a(x):(x^2+px+q).$$

It gives finally the remainder  $b(p,q)x+c(p,q)$ where $b(p,q)$ and $c(p,q)$ belong to $\mathbb{Z}[p,q]$.  According to the parent entry (http://planetmath.org/EliminationOfUnknown) we bring the system

$\{\begin{array}{cc}b(p,q)=\mathrm{\hspace{0.33em}0}\hfill & \\ c(p,q)=\mathrm{\hspace{0.33em}0}\hfill & \end{array}$

to the form

$\{\begin{array}{cc}\overline{b}(q)=\mathrm{\hspace{0.33em}0}\hfill & \\ \overline{c}(p,q)=\mathrm{\hspace{0.33em}0}\hfill & \end{array}$

and then can determine the possible rational solutions  $(p,q)$  of the system via a finite number of tests.  Hencewe find the possible quadratic factors (1) having rational coefficients.  Such a factor is converted into a primitive one when it is multiplied by the gcd of the denominators of $p$ and $q$.

Determining a possible cubic factor $x^3+p{x}^2+qx+r$ with rational coefficients requires examination of a remainder of the form

$$b(p,q,r)x^2+c(p,q,r)x+d(p,q,r).$$

In the needed system

$\{\begin{array}{cc}b(p,q,r)=\mathrm{\hspace{0.33em}0}\hfill & \\ c(p,q,r)=\mathrm{\hspace{0.33em}0}\hfill & \\ d(p,q,r)=\mathrm{\hspace{0.33em}0}\hfill & \end{array}$

we have to perform two eliminations.  Then we can act as above and find a primitive cubic factor of $a(x)$.  Similarly also the primitive factors of higher degree.  All in all, one needs only look for factors of degree $\le \frac{n}{2}$.