460 ALGEBRAIC SYSTEMS [APP. B
B.31.Prove Theorem B.18: Supposef(t)is a polynomial over a fieldK, and deg(f)=n. Thenf(t)has at
mostnroots.
The proof is by induction onn.Ifn=1, thenf(t)=at+bandf(t)has the unique roott=−b/a. Suppose
n>1. Iff(t)has no roots, then the theorem is true. Supposea∈Kis a root off(t). Then
f(t)=(t−a)g(t) (1)where deg(g)=n−1. We claim that any other root off(t)must also be a root of g(t).
Supposeb=ais another root off(t). Substitutingt=bin (1) yields 0=f(b)=(b−a)g(b).
SinceKhas no zero divisors andb−a=0, we must haveg(b)=0. By induction,g(t)has at mostn−1 roots. Thus
f(t)has at mostn−1 roots other thana. Thusf(t)has at mostnroots.B.32.Prove Theorem B.19: Suppose a rational numberp/q(reduced to lowest terms) is a root of the polynomial
f(t)=antn+···+a 1 t+a 0where all the coefficientsan,...,a 1 ,a 0 are integers. Thenpdivides the constant terma 0 andqdivides
the leading coefficientsan. In particular, ifc=p/qis an integer, thencdivides the constant terma 0.
Substitutet=p/qintof(t)=0 to obtainan(p/q)n+···+a 1 (p/q)+a 0 =0. Multiply both sides of the
equation byqnto obtainanpn+an− 1 pn−^1 q+an− 2 pn−^2 q^2 +···+a 1 pqn−^1 +a 0 qn= 0 (1)Sincepdivides all of the firstnterms of (1),pmust divide the last terma 0 qn. Assumingpandqare relatively
prime,pdividesa 0. Similarly,qdivides the lastnterms of (1), henceqdivides the first termanpn. Sincepandqare
relatively prime,qdividesan.B.33.Prove Theorem B.20: The ringK[t]of polynomials over a fieldKis a principal ideal domain (PID).
IfJis an ideal inK[t], then there exists a unique monic polynomialdwhich generatesJ, that is, every
polynomialfinJis a multiple ofd.
Letdbe a polynomial of lowest degree inJ. Since we can multiplydby a nonzero scalar and still remain inJ,
we can assume without loss in generality thatdis a monic polynomial (leading coefficient equal 1). Now suppose
f∈J. By the division algorithm there exist polynomialsqandrsuch thatf=qd+rwhere eitherr≡0or
deg(r)<deg(d). Nowf, d∈Jimpliesqd∈Jand hencer=f−qd∈J. Butdis a polynomial of lowest degree
inJ. Accordingly,r≡0 andf=qd, that is,ddividesf. It remains to show thatdis unique. Ifd′is another monic
polynomial which generatesJ, thenddividesd′andd′dividesd. This implies thatd=d′, becausedandd′are
monic. Thus the theorem is proved.
B.34.Prove Theorem B.21: Letfandgbe polynomials inK[t], not both the zero polynomial. Then there exists a
unique monic polynomialdsuch that: (i)ddivides bothfandg. (ii) Ifd′dividesfandg, thend′dividesd.
The setI={mf+ng|m, n∈K[t]}is an ideal. Letdbe the monic polynomial which generatesI. Note
f, g∈I; henceddividesfandg. Now supposed′dividesfandg. LetJbe the ideal generated byd′. Thenf, g∈J
and henceI⊆J. Accordingly,d∈Jand sod′dividesdas claimed. It remains to show thatdis unique. Ifd 1 is
another (monic) greatest common divisor offandg, thenddividesd 1 andd 1 dividesd. This implies thatd=d 1
becausedandd 1 are monic. Thus the theorem is proved.
B.35.Prove Corollary B.22: Letdbe the greatest common divisor offandg. Then there exist polynomialsm
andnsuch thatd=mf+ng. In particular, iffandgare relatively prime, then there exist polynomials
mandnsuch thatmf+ng=1.
From the proof of Theorem B.21 in Problem B.34, the greatest common divisord generates the ideal
I={mf+ng|m, n∈K[t]}. Thus there exist polynomialsmandnsuch thatd=mf+ng.
B.36.Prove Lemma B.23: Supposep∈ K[t]is irreducible. Ifpdivides the productfgof polynomials
f, g∈K[t], thenpdividesforpdividesg. More generally, ifpdivides the productf 1 f 2 ···fnofn
polynomials, thenpdivides one of them.