
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 _{1},...,_{n+1},_{1},...,_{n+1} be elements of F with _{1},...,_{n+1} distinct. The Lagrange interpolation formula allows us to construct a polynomial f F[X] of degree at most n such that
(1)
f( _{i}) = _{i} (1 < i < n + 1).
In fact, a polynomial f which works is given by
(2)
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
(3)
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 _{1},...,_{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 _{1},...,_{n+1},_{1},..._{n+1} F with _{1},...,_{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 _{1},..._{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 _{0},...,_{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 _{0} S(_{0}), _{1} S(_{1}),...,_{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 (_{0},...,_{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^{3}  3X^{2} + 4X + 1. Then s = 1, and since f(0) = 10, f(1) = 30, we may set _{1} = 0, _{2} = 1. Then S(_{1}) = {1,1}, S(_{2}) = {3,3,1,1}. Note that if g corresponds to (_{1},_{2}), then g corresponds to (_{1},_{2}), so that is enough to check the cases
( _{1}, _{2} = (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 = a_{0}+a_{1}X+...+a_{n}X^{n} Z[X] be primitive and let p be prime. Assume that pa_{i} (0 < i < n1), pa_{n}, p^{2}a_{0}. Then f is irreducible in Z[X].
Proof: Let us reason by contradiction. Assume that
f = (b _{0} + ... + b _{t}X ^{t})(c _{0}+... + c _{u}X ^{u}); b _{i},c _{i} Z,
where t > 1, u > 1. Since a_{0} = b_{0}c_{0} and since p^{2}a_{0}, we see that p cannot divide both of b_{0} and c_{0}. On the other hand, since pa_{0}, p divides one of b_{0},c_{0}. Assume that pb_{0} and pc. 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,
a_{v} = b_{v}c_{0} + b_{v1}c_{1} + ... + b_{0}c_{v}.
By assumption, pa_{v}. Moreover, pc_{0}, pc_{1},...,pc_{v1} by the choice of v. Therefore, pb_{0}c_{v}, which contradicts the facts pc_{v}, pb_{0}.
Example 1: X^{3} + 3X^{2} + 9X + 6 is irreducible in Z[X]. (set p = 3). f(X + 1) = X^{4} + X^{3} + X^{2} + X + 1 is irreducible in F[X]. Indeed since
f(X + 1) = X^{4} + 5X^{3} + 10X^{2} + 10X + 5,
we see that f(X + 1) is irreducible in Z[X]. Thus f is irreducible in Z[X].
