Make your own free website on Tripod.com
We say that R is a unique factorization domain if the following two conditions are satisfied: (1) If x element of Rx is not a unit of R, then x can be written as a product of irreducible elements of R.and (2) If x element of Rx is not a unit of R, and if x = pi1 ... pis = lambda1 ... lambdat are two expressions of x as a product of irreducible elements, then s = t and it is possible to renumber pi1 ... pis so that pi1 and lambda1 are associates (1 < i < s). Let f = a0 + a1X + ... + anXn, ai element of R, be a nonzero polynomial. If a0,...,an are relatively prime, then we say that f is primitive The set of integers. The set of rational numbers.

Factorization of Polynomials in Q[X]

Since Q[X] is a UFD, every nonconstant polynomial f element of 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 alpha1,...,alphan+1,beta1,...,betan+1 be elements of F with alpha1,...,alphan+1 distinct. The Lagrange interpolation formula allows us to construct a polynomial f element of F[X] of degree at most n such that

(1)
f(alphai) = betai   (1 < i < n + 1).

In fact, a polynomial f which works is given by

(2)
Lagrange interpolation

Lemma 1: Let f element of F[X], alpha element of F. if f(alpha) = 0, then X - alpha | 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

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

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

Proposition 2: Let alpha1,...,alphan+1,beta1,...betan+1 element of F with alpha1,...,alphan+1 distinct. Then there exists one and only one polynomial f element of F[X] such that deg(f) < n and f(alphai) = betai (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 alpha1,...alphan+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 element of 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 element of 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 alpha, g(alpha)|f(alpha). In particular, if f(alpha)not equal0, then g(alpha) is a divisor of f(alpha) and there are only finitely many choices for g(alpha). Since f has at most n zeros in Z, among the integers 1,2,3,...,2n, we may select s + 1 of them, say alpha0,...,alphas, such that f(alphai)not equal0 (0 < i < s). For each alphai let us compute S(alphai) = the set of divisors of f(alphai). Then by our observations above g(alphai) element of S(alphai), deg(g) < s. Moreover, if beta0 element of S(alpha0), beta1 element of S(alpha1),...,betaz element of S(alphas), then there exists one and only one g such that deg(g) < s and g(alphai = betai (0 < i < s), and this particular g can be calculated using (2).Thus our plan of calculation is clear. For each (s+1)-tuple (beta0,...,betas), betai element of S(alphai), 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 = X3 - 3X2 + 4X + 1. Then s = 1, and since f(0) = 1not equal0, f(1) = 3not equal0, we may set alpha1 = 0, alpha2 = 1. Then S(alpha1) = {1,-1}, S(alpha2) = {3,-3,1,-1}. Note that if g corresponds to (beta1,beta2), then -g corresponds to (-beta1,-beta2), so that is enough to check the cases

(beta1,beta2 = (1,3), (1,-3), (1,1), (1,-1).

In these cases, the value of g is respectively

2X + 1,  4X + 1,   1,   -2X + 1.

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 = a0+a1X+...+anXn element of Z[X] be primitive and let p be prime. Assume that p|ai (0 < i < n-1), pdoes not dividean, p2does not dividea0. Then f is irreducible in Z[X].

Proof: Let us reason by contradiction. Assume that

f = (b0 + ... + btXt)(c0+... + cuXu);   bi,cielement of Z,

where t > 1, u > 1. Since a0 = b0c0 and since p2does not dividea0, we see that p cannot divide both of b0 and c0. On the other hand, since p|a0, p divides one of b0,c0. Assume that pdoes not divideb0 and p|c. Since f is primitive, not all ci are divisible by p. Let cv be the first ci which is not divisible by p. Then,

av = bvc0 + bv-1c1 + ... + b0cv.

By assumption, p|av. Moreover, p|c0, p|c1,...,p|cv-1 by the choice of v. Therefore, p|b0cv, which contradicts the facts pdoes not dividecv, pdoes not divideb0.

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

f(X + 1) = X4 + 5X3 + 10X2 + 10X + 5,

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