1.13. POLYNOMIALS 23

where degree of r (λ ) is less than that of ψ (λ ). Then dividing r (λ ) by the leading coeffi-cient if necessary and denoting the result by ψ1 (λ ) , it follows the degree of ψ1 (λ ) is lessthan the degree of ψ (λ ) and ψ1 (λ ) equals for some a ∈ F

ψ1 (λ ) = (φ 1 (λ )−ψ (λ ) l (λ ))a

=

(φ 1 (λ )−

p

∑i=1

ri (λ )φ i (λ ) l (λ )

)a

=

((1− r1 (λ ))φ 1 (λ )+

p

∑i=2

(−ri (λ ) l (λ ))φ i (λ )

)a

This is one of the polynomials in S. Therefore, ψ (λ ) does not have the smallest degreeafter all because the degree of ψ1 (λ ) is smaller. This is a contradiction. Therefore, ψ (λ )divides φ 1 (λ ) . Similarly it divides all the other φ i (λ ).

If p(λ ) divides all the φ i (λ ) , then it divides ψ (λ ) because of the formula for ψ (λ )which equals ∑

pi=1 ri (λ )φ i (λ ) . Thus ψ (λ ) satisfies the condition to be the greatest com-

mon divisor. This shows the greatest common divisor exists and equals the above descrip-tion of it. ■

Lemma 1.13.7 Suppose φ (λ ) and ψ (λ ) are monic polynomials which are irreducible andnot equal. Then they are relatively prime.

Proof: Suppose η (λ ) is a nonconstant polynomial. If η (λ ) divides φ (λ ) , then sinceφ (λ ) is irreducible, φ (λ ) = η (λ ) ã for some constant ã. Thus η (λ ) equals aφ (λ ) forsome a ∈ F. If η (λ ) divides ψ (λ ) then it must be of the form bψ (λ ) for some b ∈ F andso it follows

η (λ ) = aφ (λ ) = bψ (λ ) ,

ψ (λ ) =ab

φ (λ )

but both ψ (λ ) and φ (λ ) are monic polynomials which implies a= b and so ψ (λ ) = φ (λ ).This is assumed not to happen. It follows the only polynomials which divide both ψ (λ )and φ (λ ) are constants and so the two polynomials are relatively prime. Thus a polynomialwhich divides them both must be a constant, and if it is monic, then it must be 1. Thus 1 isthe greatest common divisor. ■

Lemma 1.13.8 Let ψ (λ ) be an irreducible monic polynomial not equal to 1 which divides

p

∏i=1

φ i (λ )ki , ki a positive integer,

where each φ i (λ ) is an irreducible monic polynomial not equal to 1. Then ψ (λ ) equalssome φ i (λ ) .

Proof : Say ψ (λ ) l (λ ) = ∏pi=1 φ i (λ )

ki . Suppose ψ (λ ) ̸= φ i (λ ) for all i. Then byLemma 1.13.7, there exist polynomials mi (λ ) ,ni (λ ) such that

1 = ψ (λ )mi (λ )+φ i (λ )ni (λ )

φ i (λ )ni (λ ) = 1−ψ (λ )mi (λ )