tended meaning is the former, we shall generally write this as, say,

a · (b + c) or (b + c)a, and if the intended meaning is the latter, we

shall generally write this as a[ b + c ].

So as to keep the distinction between ring elements and indetermi-

nates clear, we shall use the symbol “X” only to denote the latter.

Also, for a polynomial a ∈ R[X], we shall in general write this simply

9.2 Polynomial rings 223

as “a,” and not as “a(X).” Of course, the choice of the symbol “X”

is arbitrary; occasionally, we may use other symbols, such as “Y,” as

alternatives.

9.2.2 Basic properties of polynomial rings

Let R be a ring. For non-zero a ∈ R[X], if a = k ai Xi with ak = 0R ,

i=0

then we call k the degree of a, denoted deg(a), we call ak the leading

coe¬cient of a, denoted lc(a), and we call a0 the constant term of a. If

lc(a) = 1R , then a is called monic.

k i i

Suppose a = i=0 ai X and b = i=0 bi X are polynomials such that

ak = 0R and b = 0R , so that deg(a) = k and lc(a) = ak , and deg(b) =

and lc(b) = b . When we multiply these two polynomials, we get

ab = a0 b0 + (a0 b1 + a1 b0 )X + · · · + ak b Xk+ .

In particular, deg(ab) ¤ deg(a) + deg(b). If either of ak or b are not zero

divisors, then ak b is not zero, and hence deg(ab) = deg(a) + deg(b). How-

ever, if both ak and b are zero divisors, then we may have ak b = 0R ,

in which case, the product ab may be zero, or perhaps ab = 0R but

deg(ab) < deg(a) + deg(b).

Example 9.28. Over the ring Z6 , consider the polynomials a := [1] + [2]X

and b = [1] + [3]X. We have ab = [1] + [5]X + [6]X2 = [1] + [5]X. Thus,

deg(ab) = 1 < 2 = deg(a) + deg(b). 2

For the zero polynomial, we establish the following conventions: its leading

coe¬cient and constant term are de¬ned to be 0R , and its degree is de¬ned

to be ’∞. With these conventions, we may succinctly state that

for all a, b ∈ R[X], we have deg(ab) ¤ deg(a) + deg(b), with

equality guaranteed to hold unless the leading coe¬cients of

both a and b are zero divisors.

In the case where the ring of coe¬cients is as integral domain, we can say

signi¬cantly more:

Theorem 9.11. Let D be an integral domain. Then:

(i) for all a, b ∈ D[X], we have deg(ab) = deg(a) + deg(b);

(ii) D[X] is an integral domain;

(iii) (D[X])— = D— .

Proof. Exercise. 2

224 Rings

9.2.3 Division with remainder

An extremely important property of polynomials is a division with remainder

property, analogous to that for the integers:

Theorem 9.12 (Division with remainder property). Let R be a ring.

For a, b ∈ R[X] with b = 0R and lc(b) ∈ R— , there exist unique q, r ∈ R[X]

such that a = bq + r and deg(r) < deg(b).

Proof. Consider the set S of polynomials of the form a’zb with z ∈ R[X]. Let

r = a ’ qb be an element of S of minimum degree. We must have deg(r) <

deg(b), since otherwise, we would have r := r ’ (lc(r) lc(b)’1 Xdeg(r)’deg(b) ) ·

b ∈ S, and deg(r ) < deg(r), contradicting the minimality of deg(r).

That proves the existence of r and q. For uniqueness, suppose that a =

bq + r and a = bq + r , where deg(r) < deg(b) and deg(r ) < deg(b). This

implies r ’ r = b · (q ’ q ). However, if q = q , then

deg(b) > deg(r ’ r) = deg(b · (q ’ q )) = deg(b) + deg(q ’ q ) ≥ deg(b),

which is impossible. Therefore, we must have q = q , and hence r = r . 2

If a = bq + r as in the above theorem, we de¬ne a mod b := r. Clearly,

b | a if and only if a mod b = 0R . Moreover, note that if deg(a) < deg(b),

then q = 0 and r = a; otherwise, if deg(a) ≥ deg(b), then q = 0 and

deg(a) = deg(b) + deg(q).

As a consequence of the above theorem, we have:

Theorem 9.13. For a ring R and a ∈ R[X] and ± ∈ R, a(±) = 0R if and

only if (X ’ ±) divides a.

Proof. If R is the trivial ring, there is nothing to prove, so assume that R is

non-trivial. Let us write a = (X ’ ±)q + r, with q, r ∈ R[X] and deg(r) < 1,

which means that r ∈ R. Then we have a(±) = (± ’ ±)q(±) + r = r. Thus,

a(±) = 0R if and only if a mod (X ’ ±) = 0R , which holds if and only if X ’ ±

divides a. 2

With R, a, ± as in the above theorem, we say that ± is a root of a if

a(±) = 0R .

Theorem 9.14. Let D be an integral domain, and let a ∈ D[X], with

deg(a) = k ≥ 0. Then a has at most k roots.

Proof. We can prove this by induction. If k = 0, this means that a is a

non-zero element of D, and so it clearly has no roots.

Now suppose that k > 0. If a has no roots, we are done, so suppose that

9.2 Polynomial rings 225

a has a root ±. Then we can write a = (X ’ ±)q, where deg(q) = k ’ 1. Now,

for any root β of a with β = ±, we have 0D = a(β) = (β ’ ±)q(β), and using

the fact that D is an integral domain, we must have q(β) = 0D . Thus, the

only roots of a are ± and the roots of q. By induction, q has at most k ’ 1

roots, and hence a has at most k roots. 2

Theorem 9.14 has many applications, among which is the following beau-

tiful theorem that establishes an important property of the multiplicative

structure of an integral domain:

Theorem 9.15. Let D be an integral domain and G a subgroup of D— of

¬nite order. Then G is cyclic.

Proof. Let n be the order of G, and suppose G is not cyclic. Then by

Theorem 8.40, we have that the exponent m of G is strictly less than n. It

follows that ±m = 1D for all ± ∈ G. That is, all the elements of G are roots

of the polynomial Xm ’ 1D ∈ D[X]. But since a polynomial of degree m over

D has at most m roots, this contradicts the fact that m < n. 2

As a special case of Theorem 9.15, we have:

Theorem 9.16. For any ¬nite ¬eld F , the group F — is cyclic. In particular,

if p is prime, then Z— is cyclic; that is, there is a primitive root modulo p.

p

Exercise 9.11. Let D be an in¬nite integral domain, and let a ∈ D[X]. Show

that if a(±) = 0D for all ± ∈ D, then a = 0D . Thus, for an in¬nite integral

domain D, there is a one-to-one correspondence between polynomials over

D and polynomial functions on D.

Exercise 9.12. This exercise develops a message authentication scheme

(see §6.7.2) that allows one to hash long messages using a relatively small

set of hash functions. Let F be a ¬nite ¬eld of cardinality q and let t be

a positive integer. Let A := F —t and Z := F . De¬ne a family H of hash

functions from A to Z as follows: let H := {h±,β : ±, β ∈ F }, where for all

h±,β ∈ H and all (a1 , . . . , at ) ∈ A, we de¬ne

t

ai ±i ∈ Z.

h±,β (a1 , . . . , at ) := β +

i=1

Show that H is a t/q-forgeable message authentication scheme. (Compare

this with the second pairwise independent family of hash functions discussed

in Example 6.25, which is much larger, but which is only 1/q-forgeable; in

practice, using the smaller family of hash functions with a somewhat higher

forging probability may be a good trade-o¬.)

226 Rings

Exercise 9.13. This exercise develops an alternative proof of Theorem 9.15.

Let n be the order of the group. Using Theorem 9.14, show that for all

d | n, there are at most d elements in the group whose multiplicative order

divides d. From this, deduce that for all d | n, the number of elements of

multiplicative order d is either 0 or φ(d). Now use Theorem 2.11 to deduce

that for all d | n (and in particular, for d = n), the number of elements of

multiplicative order d is equal to φ(d).

Exercise 9.14. Let F be a ¬eld of characteristic other than 2, so that the

2F = 0F . Show that the familiar quadratic formula holds for F . That is,

for a, b, c ∈ F with a = 0F , the polynomial f := aX2 + bX + c ∈ F [X] has

a root if and only if there exists z ∈ F such that z 2 = d, where d is the

discriminant of f , de¬ned as d := b2 ’ 4ac, and in this case the roots of f

are