Factorization of Polynomials in Q[X]

Since Q[X] is a UFD, every nonconstant polynomial f Q[X] can be factored into a product of irreducible polynomials. This is guaranteed by our general theory. However, our general theory provides us with no way which this factorization can be carried out in particular cases. No doubt, the reader has factored many polynomials in elementary algebra. However, the methods used there are usually ad hoc, depending on a series of tricks. Moreover, these methods provide no real insight into the reducibility or irreducibility of a given polynomial.

In this section we will use the theory we have developed in order to provide a computational procedure for factoring polynomials in Q[X], This beautiful development is due to the German Mathematician Kronecker. Kronecker believed that mathematics should concern itself only with objects which can be computed or constructed in a finite number of steps. Thus, for Kronecker, a proof which asserts the existence of a mathematical object, without prescribing a recipe for constructing the object in a finite number of steps, is no proof at all. The developments of this section are very much in the spirit of Kronecker's philosophy.

First, let us make a few observations concerning polynomials. Let F be a field and let ₁,...,_n+1,₁,...,_n+1 be elements of F with ₁,...,_n+1 distinct. The Lagrange interpolation formula allows us to construct a polynomial f F[X] of degree at most n such that

f(_i) = _i   (1 < i < n + 1).

In fact, a polynomial f which works is given by

Lemma 1: Let f F[X], F. if f() = 0, then X - | f. Thus, if deg(f) = n and f has more than n zeros in F, then f = 0.

Proof: By the division algorithm in F[X], there exist polynomials g and r such that

f = g(X - ) + r,  deg(r) < deg(X - ) = 1.

Setting X = in (3), we see that r() = 0. But since deg(r) < 0, r is a constant polynomial and r = 0. Thus, f = g(X - ) and X - |f. If deg(f) = n and f has zeros ₁,...,_n+1 in F, then X - _i|f (1 < i < n+1), so that (X - 1)···(X - _n+1)|f. Therefore, f = 0.

Proposition 2: Let ₁,...,_n+1,₁,..._n+1 F with ₁,...,_n+1 distinct. Then there exists one and only one polynomial f F[X] such that deg(f) < n and f(_i) = _i (1 < i < n + 1).

Proof: The existence of f is guaranteed by (2). Suppose that f and f ^* satisfy the conditions of the proposition. Then deg(f - f ^*) < n and f - f ^* has the n + 1 zeros ₁,..._n+1. Therefore by Lemma 1, f - f ^* = 0.

Now let us describe Kronecker's factorization algorithm. Without loss of generality, let us restrict ourselves to consideration of a nonconstant primitive polynomial f Z[X] of degree n. Then the irreducible factors of f in Q[X] can be taken to be primitive polynomials in Z[X]. If f is not irreducible in Z[X], then f has a factor of degree < n/2. Thus in order to factor f, it suffices to determine whether f is irreducible and, if it is not, to find a factor of f of degree < n/2. For in the latter case, we can write

f = gh,    deg(g) < n/2,    g,h Z[X],

and then we can repeat the procedure to determine whether g or h is irreducible. Eventually, we will get a factorization of f into primitive, irreducible polynomials in Z[X].

Suppose that s = the largest positive integer < m/2, and suppose that g is a factor of f in Z[X], deg(g) < n/2. Then for any integer , g()|f(). In particular, if f()0, then g() is a divisor of f() and there are only finitely many choices for g(). Since f has at most n zeros in Z, among the integers 1,2,3,...,2n, we may select s + 1 of them, say ₀,...,_s, such that f(_i)0 (0 < i < s). For each _i let us compute S(_i) = the set of divisors of f(_i). Then by our observations above g(_i) S(_i), deg(g) < s. Moreover, if ₀ S(₀), ₁ S(₁),...,_z S(_s), then there exists one and only one g such that deg(g) < s and g(_i = _i (0 < i < s), and this particular g can be calculated using (2).Thus our plan of calculation is clear. For each (s+1)-tuple (₀,...,_s), _i S(_i), we construct a unique g given by (2). Then using long division, we determine whether g is a factor of f. If none of the factors so constructed work, then f is irreducible.

This algorithm is rather clumsy to carry out manually, but it is rather easy to program. Nevertheless, let us carry out an easy example. Let f = X³ - 3X² + 4X + 1. Then s = 1, and since f(0) = 10, f(1) = 30, we may set ₁ = 0, ₂ = 1. Then S(₁) = {1,-1}, S(₂) = {3,-3,1,-1}. Note that if g corresponds to (₁,₂), then -g corresponds to (-₁,-₂), so that is enough to check the cases

(₁,₂ = (1,3), (1,-3), (1,1), (1,-1).

In these cases, the value of g is respectively

However, none of these is a factor of f, so f is irreducible.

Kronecker's algorithm proceeds much more quickly if we can recognize irreducible polynomials easily. A simple test for irreducibility which is often applicable is the Eisenstein irreducibility criterion.(Eisenstein was a pupil of Gauss).

Theorem 3 (Eisenstein): Let f = a₀+a₁X+...+a_nXⁿ Z[X] be primitive and let p be prime. Assume that p|a_i (0 < i < n-1), pa_n, p²a₀. Then f is irreducible in Z[X].

Proof: Let us reason by contradiction. Assume that

f = (b₀ + ... + b_tX^t)(c₀+... + c_uX^u);   b_i,c_i Z,

where t > 1, u > 1. Since a₀ = b₀c₀ and since p²a₀, we see that p cannot divide both of b₀ and c₀. On the other hand, since p|a₀, p divides one of b₀,c₀. Assume that pb₀ and p|c. Since f is primitive, not all c_i are divisible by p. Let c_v be the first c_i which is not divisible by p. Then,

By assumption, p|a_v. Moreover, p|c₀, p|c₁,...,p|c_v-1 by the choice of v. Therefore, p|b₀c_v, which contradicts the facts pc_v, pb₀.

Example 1: X³ + 3X² + 9X + 6 is irreducible in Z[X]. (set p = 3). f(X + 1) = X⁴ + X³ + X² + X + 1 is irreducible in F[X]. Indeed since

we see that f(X + 1) is irreducible in Z[X]. Thus f is irreducible in Z[X].