Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

APP. B] ALGEBRAIC SYSTEMS 447

Theorem B.12: LetKbe an integral domain. ThenK[t]under the operations of addition and multiplication of
polynomials is a commutative ring with an identity element 1.
The following simple result has important consequences.

Lemma B.13: Supposefandgare polynomials over an integral domainK. Then

deg(f g)=deg(f )+deg(g).

The proof follows directly from the definition of the product of polynomials. Namely, suppose

f(t)=antn+···+a 1 t+a 0 and g(t)=bmtm+···+b 1 t+b 0

wherean=0 andbm=0. Thus deg(f )=nand deg(g)=m. Then

f(t)g(t)=anbmtn+m+terms of lower degree

Also, sinceKis an integral domain with no zero divisors,anbm=0. Thus

deg(f g)=m+n=deg(f )+deg(g)

and the lemma is proved.

The following proposition lists many properties of our polynomials. (Recall that a polynomialgis said to
dividea polynomialfif there exists a polynomialhsuch thatf(t)=g(t)h(t).)

Proposition B.14: LetKbe an integral domain and letfandgbe polynomials overK.

(i) K[t]is an integral domain.

(ii) The units ofK[t]are the units inK.

(iii) Ifgdividesf, then deg(g)≤deg(f )orf≡0.

(iv) Ifgdividesfandfdividesg, thenf(t)=kg(t)wherekis a unit inK.

(v) Ifdandd′are monic polynomials such thatddividesd′andd′dividesd, thend=d′.

Euclidean Algorithm, Roots of Polynomials

This subsection discusses the roots of a polynomialf(t), where we now assume the coefficients off(t)
come from a fieldK. Recall that a scalara∈Kis arootof a polynomialf(t)iff(a)=0. First we begin with
an important theorem which is very similar to a corresponding theorem for the integersZ.

Theorem B.15 (Euclidean DivisionAlgorithm): Letf(t)andg(t)be polynomials over a fieldKwithg(t)=0.
Then there exist polynomialsq(t)andr(t)such that

f(t)=q(t)g(t)+r(t)

where eitherr(t)≡0ordeg(r) <deg(g).
The above theorem (proved in Problem B.30) formalizes the process known as “long division.” The poly-
nomialq(t)is called thequotientand the polynomialr(t)is called theremainderwhenf(t)is divided byg(t).

Corollary B.16 (Remainder Theorem): Supposef(t)is divided byg(t)=t−a. Thenf(a)is the remainder.

The proof follows from the Euclidean Algorithm. That is, dividingf(t)byt−awe get

f(t)=q(t)(t−a)+r(t)

where deg(r)<deg(t−a)=1.Hencer(t)=ris a scalar. Substitutingt=ain the equation forf(t)yields

f(a)=q(a)(a−a)+r=q(t)· 0 +r=r

Thusf(a)is the remainder, as claimed.