# 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. Hence we 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}$.

## References

- 1 K. Väisälä: Lukuteorian ja korkeamman algebran alkeet. Tiedekirjasto No. 17. Kustannusosakeyhtiö Otava, Helsinki (1950).

Title | factorization of primitive polynomial |
---|---|

Canonical name | FactorizationOfPrimitivePolynomial |

Date of creation | 2013-03-22 19:20:30 |

Last modified on | 2013-03-22 19:20:30 |

Owner | pahio (2872) |

Last modified by | pahio (2872) |

Numerical id | 4 |

Author | pahio (2872) |

Entry type | Algorithm |

Classification | msc 12D99 |

Classification | msc 26C05 |

Synonym | primitive factors of primitive polynomial |

Related topic | EliminationOfUnknown |