1.4. Factoring polynomials.

Back

 It will frequently be important for us to know whether a

polynomial is irreducible and, if it isn’t, what its factors are. The following results help.

Proposition 1.4. Suppose r = c

d , c, d ∈ Z, gcd(c, d) = 1, is a root of a polynomial

amXm + am−1Xm−1 + ・ ・ ・ + a0, ai ∈ Z.

Then c|a0 and d|am.

Proof. It is clear from the equation

amcm + am−1cm−1d + ・ ・ ・ + a0dm = 0

that d|amcm, and therefore, d|am. The proof that c|a0 is similar.

Example 1.5. The polynomial X3−3X−1 is irreducible in Q[X] because its only possible

roots are Ѓ}1 (and they aren’t).

Proposition 1.6. Let f(X) ∈ Z[X] be such that its coefficients have greatest common

divisor 1. If f(X) factors nontrivially in Q[X], then it factors nontrivially in Z[X]; moreover,

if f(X) ∈ Z[X] is monic, then any monic factor of f(X) in Q[X] lies in Z[X].

FIELDS AND GALOIS THEORY 3

Proof. Use Gauss’s lemma (see Jacobson, 2.16, or Math 593).

Proposition 1.7. (Eisenstein criterion) Let

f = amXm + am−1Xm−1 + ・ ・ ・ + a0, ai ∈ Z;

suppose that there is a prime p such that:

p does not divide am,

p divides am−1, ..., a0,

p2 does not divide a0.

Then f is irreducible in Q[X].

Proof. We may remove any common factor from the coefficients f, and hence assume

that they have gcd = 1. Therefore, if f(X) factors in Q[X], it factors in Z[X]:

amXm + am−1Xm−1 + ・ ・ ・ + a0 = (bnXn + ・ ・ ・ + b0)(crXr + ・ ・ ・ + c0), bi, ci ∈ Z, n,r<m.

Since p, but not p2, divides a0 = b0c0, p must divide exactly one of b0, c0, say p divides b0.

Now from the equation

a1 = b0c1 + b1c0,

we see that p|b1. Now from the equation

a2 = b0c2 + b1c1 + b2c0,

we see that p|b2. By continuing in this way, we find that p divides b0, b1, . . . , bn, which

contradicts the fact that p does not divide am.

The above three propositions hold with Z replaced by any unique factorization domain.

Proposition 1.8. There is an algorithm for factoring a polynomial in Q[X].

Proof. Consider f(X) ∈ Q[X]. Multiply f(X) by an integer, so that it is monic, and

then replace it by Ddeg(f)f(X

D), D = a common denominator for the coefficients of f, to obtain

a monic polynomial with integer coefficients. Thus we need consider only polynomials

f(X) = Xm + a1Xm−1 + ・ ・ ・ + am, ai ∈ Z.

From the fundamental theorem of algebra (see later), we know that f splits completely in

C[X]:

f(X) =

_m

i=1

(X − αi), αi ∈ C.

From the equation f(αi) = 0, it follows that |αi| is less than some bound M depending on

a1, . . . , am. Now if g(X) is a monic factor of f(X), then its roots in C are certain of the αi,

and its coefficients are symmetric polynomials in its roots. Therefore the absolute values of

the coefficients of g(X) are bounded. Since they are also integers (by 1.6), we see that there

are only finitely many possibilities for g(X). Thus, to find the factors of f(X) we (better

Maple) only have to do a finite amount of checking.

One other observation is sometimes useful: Suppose that the leading coefficient of f(X) ∈

Z[X] is not divisible by the prime p;if f(X) is irreducible in Fp[X], then it is irreducible

in Z[X]. Unfortunately, this test is not always effective: for example, X4 − 10X2 + 1 is

reducible1 modulo every prime, but it is irreducible in Q[X].

1I don’t know an elementary proof of this. One proof uses that its Galois group is ≈ (Z/2Z)2.

4 J.S. MILNE

Maple knows how to factor polynomials in Q[X] and in Fp[X]. For example

>factor(6*X^2+18*X-24);w ill find the factors of 6X2 + 18X − 24, and

>Factor(X^2+3*X+3) mod 7;w ill find the factors of X2+3X +3 modulo 7, i.e., in F7[X].

Thus, we need not concern ourselves with the problem of factorizing polynomials in Q[X] or

Fp[X].

Навигация