1.8. Polynomials

i

“bookmt” — 2006/8/8 — 12:58 — page 44 — #56

i

i

44

1. ALGEBRAIC THEMES (c) Solve the congruence 8x  12 .mod 125/.

1.7.15. This exercise guides you to a proof of the Chinese remainder theorem.

(a) To prove the Chinese remainder theorem, show that it suffices to find m and n such that ˛ C ma D ˇ C nb.

(b) To find m and n as in part (a), show that it suffices to find s and t such that as C bt D .˛ ˇ/.

(c) Show that the existence of s and t as in part (b) follows from a and b being relatively prime.

1.7.16. Find and integer x such that x  3 .mod 4/ and x  5 .mod 9/.

1.8. Polynomials Let K denote the set Q of rational numbers, the set R of real numbers, or the set C of complex numbers. (K could actually be any field; fields are algebraic systems that generalize the examples Q, R, and C; we will give a careful definition of fields later.)

Polynomials with coefficients in K are expressions of the form anxnC an 1xn 1 C    C a0, where the ai are elements in K. The set of all polynomials with coefficients in K is denoted by KŒx. Addition and multiplication of polynomials are defined according to the familiar rules:

X

X

X .

aj xj / C .

bj xj / D .aj C bj /xj ;

j

j

j

and

X

X X X .

ai xi /.

bj xj / D .ai bj /xiCj

i

j

i

j

X

X X X

D .

ai bj /xk D .

ai bk i /xk:

k

i;j W iCj Dk

k

i

I trust that few readers will be disturbed by the informality of defining polynomials as “an expression of the form ...” . However, it is possible to formalize the concept by defining a polynomial to be an infinite sequence of elements of K, with all but finitely many entries equal to zero (namely, the sequence of coefficients of the polynomial). Thus 7x2 C 2x C 3 would be interpreted as the sequence .3; 2; 7; 0; 0; : : : /. The operations of addition and multiplication of polynomials can be recast as operations on such functions. It is straightforward (but not especially enlightening) to carry this out.

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 45 — #57

i

i

1.8. POLYNOMIALS

45

Example 1.8.1.

.2x3 C 4x C 5/ C .5x7 C 9x3 C x2 C 2x C 8/ D 5x7 C 11x3 C x2 C 6x C 13;

and

.2x3 C 4x C 5/.5x7 C 9x3 C x2 C 2x C 8/ D 10 x10 C 20 x8 C 25 x7 C 18 x6 C 2 x5 C 40 x4 C 65 x3 C 13 x2 C 42 x C 40:

K can be regarded as subset of KŒX , and the addition and multiplica tion operations on KŒx extend those on K; that is, for any two elements in K, their sum and product as elements of K agree with their sum and product as elements of KŒx.

The operations of addition and multiplication of polynomials satisfy properties exactly analogous to those listed for the integers in Proposition 1.6.1; see Proposition 1.8.2 on the next page.

All of these properties can be verified by straightforward computa tions, using the definitions of the operations and the corresponding properties of the operations in K.

As an example of the sort of computations needed, let us verify the dis tributive law: Let f .x/ D P`iD0 aixi, g.x/ D PnjD0 bj xj , and h.x/ D

Pn j D0 cj xj . Then

`

n

n

X

X

X f .x/.g.x/ C h.x// D .

ai xi /.

bj xj C cj xj /

i D0 j D0 j D0

`

n

X

X

D

ai xi .

.bj C cj /xj / i D0 j D0

`

n

X X

D ai .bj C cj /xiCj i D0 j D0 `

n

X X

D .ai bj C ai cj /xiCj i D0 j D0 `

n

`

n

X X

X X

D .ai bj /xiCj C .ai cj /xiCj i D0 j D0 i D0 j D0 `

n

`

n

X

X

X

X D .

ai xi /.

bj xj / C .

ai xi /.

cj xj /

i D0 j D0 i D0 j D0 D f .x/g.x/ C f .x/h.x/:

Verification of the remaining properties listed in the following propo sition is left to the reader.

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 46 — #58

i

i

46

1. ALGEBRAIC THEMES

Proposition 1.8.2.

(a) Addition in KŒx is commutative and associative; that is, for all f; g; h 2 KŒx, f C g D g C f; and f C .g C h/ D .f C g/ C h: (b) 0 is an identity element for addition; that is, for all f 2 KŒx, 0 C f D f: (c) Every element f of KŒx has an additive inverse f , satisfying f C . f / D 0: (d) Multiplication in KŒx is commutative and associative; that is, for all f; g; h 2 KŒx, fg D gf; and f .gh/ D .fg/h:

(e) 1 is an identity for multiplication; that is, for all f 2 KŒx, 1f D f: (f) The distributive law holds: For all f; g; h 2 KŒx, f .g C h/ D fg C f h: Definition 1.8.3. The degree of a polynomial Pk akxk is the largest k such that ak ¤ 0. (The degree of a constant polynomial c is zero, unless c D 0. By convention, the degree of the constant polynomial 0 is 1.)

The degree of p 2 KŒx is denoted deg.p/.

If p D Pj aj xj is a nonzero polynomial of degree k, the leading coefficient of p is ak and the leading term of p is akxk. A polynomial is said to be monic if its leading coefficient is 1.

p

Example 1.8.4. The degree of p D .=2/x7 C ix4 2x3 is 7; the leading coefficient is =2; .2=/p is a monic polynomial.

Proposition 1.8.5. Let f; g 2 KŒx.

(a) deg.fg/ D deg.f / C deg.g/; in particular, if f and g are both nonzero, then fg ¤ 0.

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 47 — #59

i

i

1.8. POLYNOMIALS

47

(b) deg.f C g/  maxfdeg.f /; deg.g/g.

Proof. Exercise 1.8.3.

n

We say that a polynomial f divides a polynomial g (or that g is divis ible by f ) if there is a polynomial q such that f q D g. We write f jg for “f divides g.”

The goal of this section is to show that KŒx has a theory of divisibility, or factorization, that exactly parallels the theory of divisibility for the integers, which was presented in Section 1.6. In fact, all of the results of this section are analogues of results of Section 1.6, with the proofs also following a nearly identical course. In this discussion, the degree of a polynomial plays the role that absolute value plays for integers.

Proposition 1.8.6. Let f , g, h, u, and v denote polynomials in KŒx.

(a) If uv D 1, then u; v 2 K.

(b) If f jg and gjf , then there is a k 2 K such that g D kf .

(c) Divisibility is transitive: If f jg and gjh, then f jh.

(d) If f jg and f jh, then for all polynomials s; t, f j.sg C th/.

Proof. For part (a), if uv D 1, then both of u; v must be nonzero. If either of u or v had positive degree, then uv would also have positive degree.

Hence both u and v must be elements of K.

For part (b), if g D vf and f D ug, then g D uvg, or g.1 uv/ D 0.

If g D 0, then k D 0 meets the requirement. Otherwise, 1

uv D 0, so both u and v are elements of K, by part (a), and k D v satisfies the requirement.

The remaining parts are left to the reader.

n

What polynomials should be considered the analogues of prime num bers? The polynomial analogue of a prime number should be a polynomial that does not admit any nontrivial factorization. It is always possible to ”factor out” an arbitrary nonzero element of K from a polynomial f 2 KŒx, f .x/ D c.c 1f .x//, but this should not count as a genuine factorization. A nontrivial factorization f .x/ D g.x/h.x/ is one in which both of the factors have positive degree (or, equivalently, each factor has degree less than deg.f /) and the polynomial analogue of a prime number is a polynomial for which such a factorization is is not possible. Such polynomials are called irreducible rather than prime.

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 48 — #60

i

i

48

1. ALGEBRAIC THEMES

Definition 1.8.7. We say that a polynomial in KŒx is irreducible if its degree is positive and it cannot be written as a product of two polynomials each of strictly smaller (positive) degree.

The analogue of the existence of prime factorizations for integers is the following statement.

Proposition 1.8.8. Any polynomial in KŒx of positive degree can be written as a product of irreducible polynomials.

Proof. The proof is by induction on the degree. Every polynomial of degree 1 is irreducible, by the definition of irreducibility. So let f be a polynomial of degree greater than 1, and make the inductive hypothesis that every polynomial whose degree is positive but less than the degree of f can be written as a product of irreducible polynomials. If f is not itself irreducible, then it can be written as a product, f D g1g2, where 1  deg.gi /