factorization of primitive polynomial

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



be a primitive polynomial in [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 polynomialMathworldPlanetmathPlanetmathPlanetmath a(x).

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

x2+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


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

{b(p,q)= 0c(p,q)= 0

to the form

{b¯(q)= 0c¯(p,q)= 0

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 x3+px2+qx+r with rational coefficients requires examination of a remainder of the form


In the needed system

{b(p,q,r)= 0c(p,q,r)= 0d(p,q,r)= 0

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


  • 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