22 CHAPTER 1. SOME PREREQUISITE TOPICS

a polynomial having degree less than m. Therefore from the above,

a(λ )− ã(λ ) =

=r(λ )︷ ︸︸ ︷( f (λ )−q(λ )g(λ ))− b

b̂λ

m−ng(λ ) = f (λ )− q̂(λ )g(λ )

which is of the same form as ∗ having smaller degree. However, m was as small as possible.Hence m < n after all.

As to uniqueness, if you have r (λ ) , r̂ (λ ) ,q(λ ) , q̂(λ ) which work, then you wouldhave

(q̂(λ )−q(λ ))g(λ ) = r (λ )− r̂ (λ )

Now if the polynomial on the right is not zero, then neither is the one on the left. Hencethis would involve two polynomials which are equal although their degrees are different.This is impossible. Hence r (λ ) = r̂ (λ ) and so, the above lemma shows q̂(λ ) = q(λ ). ■

Definition 1.13.4 A polynomial f is said to divide 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.13.5 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 have the same degree. Hence l′ (λ ) , l (λ ) are both constants.However, this constant must be 1 because both q(λ ) and q′ (λ ) are monic. ■

Theorem 1.13.6 Let {φ i (λ )} be polynomials, not all of which are zero polynomials. Thenthere exists a greatest common divisor and it equals the monic polynomial ψ (λ ) of smallestdegree such that there exist polynomials ri (λ ) satisfying

ψ (λ ) =p

∑i=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 chosen suchthat 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, does it divideeach φ i (λ )? Suppose it fails to divide φ 1 (λ ) . Then by Lemma 1.13.3

φ 1 (λ ) = ψ (λ ) l (λ )+ r (λ )