22 CHAPTER 1. BASIC NOTIONS

Definition 1.8.6 A polynomial f is divides a polynomial g if g(λ ) = f (λ )r (λ ) forsome polynomial r (λ ). Let {φ i (λ )} be a finite set of polynomials. The greatest commondivisor will be the monic polynomial q(λ ) such that q(λ ) divides each φ i (λ ) and if p(λ )divides each φ i (λ ) , then p(λ ) divides q(λ ) . The finite set of polynomials {φ i} is said to berelatively prime if their greatest common divisor is 1. A polynomial f (λ ) is irreducible ifthere is no polynomial with coefficients in Fwhich divides it except nonzero scalar multiplesof f (λ ) and constants. In other words, it is not possible to write f (λ ) = a(λ )b(λ ) whereeach of a(λ ) ,b(λ ) have degree less than the degree of f (λ ) unless one of a(λ ) ,b(λ ) is aconstant.

Proposition 1.8.7 The greatest common divisor is unique.

Proof: Suppose both q(λ ) and q′ (λ ) work. Then q(λ ) divides q′ (λ ) and the otherway around and so q′ (λ ) = q(λ ) l (λ ) , q(λ ) = l′ (λ )q′ (λ ). Therefore, the two must havethe same degree. Hence l′ (λ ) , l (λ ) are both constants. However, this constant must be 1because both q(λ ) and q′ (λ ) are monic. ■

Theorem 1.8.8 Let {φ i (λ )} be polynomials, not all of which are zero polynomi-als. Then it follows that there exists a greatest common divisor and it equals the monicpolynomial ψ (λ ) of smallest degree such that there exist polynomials ri (λ ) satisfyingψ (λ ) = ∑

pi=1 ri (λ )φ i (λ ) .

Proof: Let S denote the set of monic polynomials of the form ∑pi=1 ri (λ )φ i (λ ). where

ri (λ ) is a polynomial. Then S ̸= /0 because some φ i (λ ) ̸= 0. Then let the ri be chosensuch that the degree of the expression ∑

pi=1 ri (λ )φ i (λ ) is as small as possible. Letting

ψ (λ ) equal this sum, it remains to verify it is the greatest common divisor. First, doesit divide each φ i (λ )? Suppose it fails to divide φ 1 (λ ) . Then by Lemma 1.8.3, φ 1 (λ ) =ψ (λ ) l (λ )+ r (λ ) where degree of r (λ ) is less than that of ψ (λ ). Then dividing r (λ ) bythe leading coefficient if necessary and denoting the result by ψ1 (λ ) , it follows the degreeof ψ1 (λ ) is less than 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.8.9 Suppose φ (λ ) and ψ (λ ) are monic polynomials which are irreducibleand not equal. Then they are relatively prime.