Put si = ri ’ r1 so that the elements v1 , . . . , v2t satisfy the following

linear equations:

+ + ··· + =

v2 ± s2 v2t ± s2t 0

v1

+ + ··· + =

v2 ± 2s2 v2t ± 2s2t 0

v1

. . .

. . .

. . .

+ + ··· + =

v2 ± 2ts2 v2t ± 2ts2t 0.

v1

The coef¬cient matrix is nonsingular because its determinant is the Vandermonde

determinant:

®

1 ± s2 · · · ± s2t

1 ± 2s2 ± 2s2t

. = (± si ’ ± sj ) = 0.

det .

°. .»

. . 2t i>j 2

··· ±

2ts2 2ts2t

1±

288 14 ERROR-CORRECTING CODES

This determinant is nonzero because ±, ± 2 , . . . , ± 2t are all different if t < 2m’1 .

[The expression for the Vandermonde determinant can be veri¬ed as follows.

When the j th column is subtracted from the ith column, each term contains

a factor (± si ’ ± sj ); hence the determinant contains this factor. Both sides are

polynomials in ± s2 , . . . , ± s2t of the same degree and hence must differ by a

multiplicative constant. By looking at the leading diagonal, we see that this

constant is 1.]

The linear equations above must have the unique solution v1 = v2 = · · · =

v2t = 0. Therefore, there are no nonzero code words with fewer than 2t + 1

ones, and, by Lemma 14.18 and Proposition 14.2, the code will correct t or

fewer errors.

There is, for example, a BCH (127,92)-code that will correct up to ¬ve errors.

This code adds 35 check digits to the 92 information digits and hence contains

235 syndromes. It would be impossible to store all these syndromes and their

coset leaders in a computer, so decoding has to be done by other methods. The

errors in BCH codes can be found by algebraic means without listing the table

of syndromes and coset leaders.

In fact, any code with a relatively high information rate must be long and

consequently, to be useful, must possess a simple algebraic decoding algorithm.

Further details of the BCH and other codes can be found in Roman [46], Lidl

and Pilz [10], and Lidl and Niederreiter [34].

EXERCISES

14.1. Which of the following received words contain detectable errors when

using the (3, 2) parity check code?

110, 010, 001, 111, 101, 000.

14.2. Decode the following words using the (3, 1) repeating code to cor-

rect errors:

111, 011, 101, 010, 000, 001.

Which of the words contain detectable errors?

14.3. An ancient method of detecting errors when performing the arithmeti-

cal operations of addition, multiplication, and subtraction is the method

known as casting out nines. For each number occurring in a calcula-

tion, a check digit is found by adding together the digits in the number

and casting out any multiples of nine. The original calculation is then

performed on these check digits instead of on the original numbers. The

answer obtained, after casting out nines, should equal the check digit of

the original answer. If not, an error has occurred. For example, check

the following:

9642 — (425 ’ 163) = 2526204.

EXERCISES 289

Add the digits of each number; 9 + 6 + 4 + 2 = 21 = 2 — 9 + 3, 4 + 2 +

5 = 9 + 2, 1 + 6 + 3 = 9 + 1. Cast out the nines and perform the calcu-

lation on these check digits:

3 — (2 ’ 1) = 3.

Now 3 is the check digit for the answer because 2 + 5 + 2 + 6 +

2 + 0 + 4 = 2 — 9 + 3; hence this calculation checks. Why does this

method work?

14.4. Find the redundancy of the English language. Copy a paragraph from a

book leaving out every nth letter, and ask a friend to try to read the para-

graph. (Try n = 2, 3, 4, 5, 6. If a passage with every ¬fth letter missing

can usually be read, the redundancy is at least 1 or 20%.)

5

14.5. Each recent book, when published, is given an International Standard

Book Number (ISBN) consisting of ten digits, for example, 0-471-29891-

3. The ¬rst digit is a code for the language group, the second set of digits

is a code for the publisher, and the third group is the publisher™s number

for the book. The last digit is one of 0, 1, 2, . . . , 9, X and is a check digit.

Have a look at some recent books and discover how this check digit is

calculated. What is the 1 — 10 parity check matrix? How many errors

does this code detect? Will it correct any?

Is 1 + x 3 + x 4 + x 6 + x 7 or x + x 2 + x 3 + x 6 a code word in the (8,4)

14.6.

polynomial code generated by p(x) = 1 + x 2 + x 3 + x 4 ?

Write down all the code words in the (6,3)-code generated by p(x) =

14.7.

1 + x2 + x3.

14.8. Design a code for messages of length 20, by adding as few check digits

as possible, that will detect single, double, and triple errors. Also give a

shift register encoding circuit for your code.

14.9. Decode the following, using the (6,3)-code given in Table 14.9:

000101, 011001, 110000.

14.10. A (7,4) linear code is de¬ned by the equations

u1 = u4 + u5 + u7 , u2 = u4 + u6 + u7 , u3 = u4 + u5 + u6 ,

where u4 , u5 , u6 , u7 are the message digits and u1 , u2 , u3 are the check

digits. Write down the generator and parity check matrices for this code.

Decode the received words 0000111 and 0001111 to correct any errors.

14.11. Find the minimum Hamming distance between the code words of the code

with generator matrix G, where

®

001011000

0 1 0 1 0 0 1 0 0

GT =

°1 0 1 0 0 0 0 1 0».

011010001

290 14 ERROR-CORRECTING CODES

Discuss the error-detecting and error-correcting capabilities of this code,

and write down the parity check matrix.

14.12. Encode the following messages using the generator matrix of the (9,4)-

code of Example 14.11:

1101, 0111, 0000, 1000.

For Exercises 14.13 to 14.15, ¬nd the generator and parity check matrices for the

polynomial codes.

The (4,1)-code generated by 1 + x + x 2 + x 3 .

14.13.

The (7,3)-code generated by (1 + x)(1 + x + x 3 ).

14.14.

The (9,4)-code generated by 1 + x 2 + x 5 .

14.15.

14.16. Find the syndromes of all the received words in the (3,2) parity

check code.

14.17. Using the parity check matrix in Example 14.14 and the syndromes in

Table 14.10, decode the following words:

101110, 011000, 001011, 111111, 110011.

14.18. Using the parity check matrix in Example 14.11 and the syndromes in

Table 14.12, decode the following words:

110110110, 001001101, 111111111, 000000111.

For Exercises 14.19 to 14.22, construct a table of coset leaders and syndromes

for each code.

14.19. The (3,1)-code generated by 1 + x + x 2 .

14.20. The (7,4)-code with parity check matrix

«

100 111 0

0 1 0 1.

H= 110

001 101 1

14.21. The (9,4)-code generated by 1 + x 2 + x 5 .

14.22. The (7,3)-code generated by (1 + x)(1 + x + x 3 ).

14.23. Consider the (63,56)-code generated by (1 + x)(1 + x + x 6 ).

(a) What is the number of digits in the message before coding?

(b) What is the number of check digits?

(c) How many different syndromes are there?

(d) What is the information rate?

(e) What sort of errors will it detect?

(f) How many errors will it correct?

EXERCISES 291

14.24. One method of encoding a rectangular array of digits is to add a parity

check digit to each of the rows and then add a parity check digit to each

of the columns (including the column of row checks). For example, in

the array in Figure 14.8, the check digits are shaded and the check on

checks is crosshatched. This idea is sometimes used when transferring

information to and from magnetic tape. The same principle is used in

accounting. Show that one error can be corrected and describe how to

correct that error. Will it correct two errors? What is the maximum number

of errors that it will detect?

101 0

011 0

110 0

Figure 14.8

14.25. Let V be a vector space over Zp , where p is a prime. Show that every

subgroup is a subspace. Is this result true for a vector space over any

Galois ¬eld?

14.26. Show that the Hamming distance between vectors has the follow-

ing properties:

(1) d(u, v) = d(v, u).

(2) d(u, v) + d(v, w) d(u, w).

(3) d(u, v) 0 with equality if and only if u = v.

(This shows that d is a metric on the vector space.)

14.27. We can use elements from a ¬nite ¬eld GF (q), instead of binary digits,

P

to construct codes. If G = is a generator matrix, show that

Ik

H = (In’k | ’ P ) is the parity check matrix.

14.28. Using elements of Z5 , ¬nd the parity check matrix of the (7,4)-code

generated by 1 + 2x + x 3 ∈ Z5 [x].

14.29. Find the generators of the two- and three-error-correcting BCH codes

of length 15 by starting with the primitive element β in GF (16), where

β 4 = 1 + β 3.

14.30. Find the generator polynomial of a single-error-correcting BCH code of

length 7.

14.31. Let ± be a primitive element in GF (32), where ± 5 = 1 + ± 2 . Find an

irreducible polynomial in Z2 [x] with ± 3 as a root.

14.32. Find the generator polynomial of a double-error-correcting BCH code of

length 31.

292 14 ERROR-CORRECTING CODES

14.33. A linear code is called cyclic if a cyclic shift of a code word is still a code

word; in other words, if a1 a2 · · · an is a code word, then an a1 a2 · · · an’1

is also a code word. Show that a binary (n, k) linear code is cyclic if

and only if the code words, considered as polynomials, form an ideal in

Z2 [x]/(x n ’ 1).

14.34. Let F be a ¬eld. Given f (x) = a0 + a1 x + a2 x 2 + · · · + an x n in F [x],

de¬ne the derivative f (x) of f (x) by f (x) = a1 + 2a2 x + · · · + nan x n .

Show that the usual rules of differentiation hold:

(a) [af (x)] = af (x).

(b) [f (x) + g(x)] = f (x) + g (x).

(c) [f (x)g(x)] = f (x)g (x) + f (x)g(x).

(d) {f [g(x)]} = f [g(x)]g (x).

[Hint for (c) and (d): Let x and y be two indeterminants over F , and write

F (x, y) for the ¬eld of fractions of the integral domain F [x, y]. Given

f (x) in F [x], let f0 (x, y) be the unique polynomial in F [x, y] such that

f (x) ’ f (y)

= f0 (x, y) in F (x, y). Show that f (x) = f0 (x, x).]

x’y

14.35. Let a be an element of a ¬eld F , and let f (x) ∈ F [x]. Show that (x ’ a)2

divides f (x) in F [x] if and only if (x ’ a) divides both f (x) and f (x).

[Hint: See Exercise 14.34.]

14.36. In n is odd, show that x n ’ 1 is square-free when factored into irreducibles

in Z2 [x]. [Hint: See Exercise 14.35.]

14.37. Write Bn = Z2 [x]/(x n ’ 1) for the factor ring, and write the coset

x + (x n ’ 1) as t = x + (x n ’ 1). Hence binary linear codes are written

as follows:

Bn (t) = {a0 + a2 t + · · · + an’1 t n’1 |ai ∈ Z2 , t n = 1}

= {f (t)|f (x) ∈ F [x], t n = 1}.

Let C denote a cyclic code (see Exercise 14.33).

(a) Show that

C = (g(t)) = {q(t)g(t)|q(t) ∈ Bn (t)}

= {f (t)|g(x)dividesf (x)in Z2 [x]}.

(b) If n is odd, show that C = (e(t)) where [e(t)]2 = e(t) in Bn (t).

Show further that e(t) is uniquely determined by C; it is called

the idempotent generator of C. [Hint: By Exercise 14.36 write

x n ’ 1 = g(x)h(x), where g(x) and h(x) are relatively prime in

Z2 [x].]

Appendix 1

PROOFS

If p and q denote statements, mathematical theorems usually take the form of

an implication: “If p is true, then q is true”. We write this in symbols as

p’q

and read it as “p implies q.” Here p is called the hypothesis, q is called the

conclusion, and the veri¬cation that p ’ q is valid is called the proof of the

implication.

Example 1. If n is an odd integer, show that n2 is odd.

Proof. We proceed by assuming that n is odd, and using that information to

show that n2 is also odd. If n is odd it has the form n = 2k + 1, where k is some

integer. Hence n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1 is also odd.

This is called the direct method of proof, where the truth of the hypothesis is

used directly to establish the truth of the conclusion.

Note that the computation that n2 = 2(2k 2 + 2k) + 1 in Example 1 depends

on other properties of arithmetic that we did not prove. In fact, proofs that p ’

q usually proceed by establishing a sequence p ’ p1 ’ p2 ’ · · · ’ pn’1 ’

pn ’ q of implications leading from p to q. Many of the intervening implications

are part of an established part of mathematics, and are not stated explicitly.

Another method is proof by reduction to cases. Here is an illustration.

Example 2. Show that n2 ’ n is even for every integer n.

Proof. This proposition may not appear to be an implication, but it can be

reformulated as: If “n is an integer,” then “n2 ’ n is even.” Given n, the idea is

to separate the proof into the two cases that n is even or odd. Since n is even in

the ¬rst case and n ’ 1 is even in the second case, we see that n2 ’ n = n(n ’ 1)

is even in either case.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

293

294 PROOFS

Note that it is important in Example 2 that every integer n is even or odd,

so that the two cases considered cover every possibility. Of course, a proof

can proceed by reduction to more than two cases, at least one of which must

always hold.

The statements used in mathematics are chosen so that they are either true

or false. This leads to another method of proof of an implication p ’ q called

proof by contradiction. Since q is either true or false, the idea is to show that it

cannot happen that both p is true and q is false. We accomplish this by showing

that the assumption that p is true and q is false leads to a contradiction.

Example 3. If r is a rational number (that is, a fraction), show that r 2 = 2.

Proof. Here we want to prove that p ’ q, where p is the statement that “r is

a fraction” and q is the statement that r 2 = 2. The idea is to show that assuming

m

that p is true and q is false leads to a contradiction. So assume that r = is a

n

m

fraction and r 2 = 2. Write in lowest terms, so, in particular, m and n are not

n

both even. The statement r 2 = 2 leads to m2 = 2n2 , so m2 is even. Hence m is

even (by Example 1), say m = 2k, where k is an integer. But then the equation

m2 = 2n2 becomes 4k 2 = 2n2 , so n2 = 2k 2 is even. Hence n is even (again by

Example 1), so we have shown that m and n are both even, contradicting the

choice of m and n. This completes the proof.

As in Example 3, proof by contradiction often provides the simplest veri¬ca-

tion of an implication.

To provide another example, we need the following concept. An integer greater

than 1 is called a prime (and we say that it is a prime number) if it cannot be

factored as the product of two smaller integers both greater than 1. Hence the ¬rst

few primes are 2, 3, 5, 7, 11, 13, . . ., but 6 = 2 · 3 and 35 = 5 · 7 are not primes.

Example 4. If 2n ’ 1 is a prime number, show that n is prime.

Proof. We must show that p ’ q where p is the statement “2n ’ 1 is prime”

and q is the statement that “n is prime.” Suppose that q is false, so that n = ab

where a 2 and b 2 are integers. For convenience, write k = 2a . Then 2n =

2ab = (2a )b = k b , and we verify that

2n ’ 1 = k b ’ 1 = (k ’ 1)(k b’1 + k b’2 + · · · + k 2 + k + 1).

Since k 4 this is a factorization of 2n ’ 1 as a product of integers greater than

2, a contradiction.

The next example illustrates one way to verify that an implication is not valid.

Example 5. Show that the implication “n is a prime” ’ “2n ’ 1 is a prime”

is false.

PROOFS 295

Proof. The ¬rst few primes are n = 2, 3, 5, and 7, and the corresponding

values 2n ’ 1 = 3, 7, 31, and 127 are all prime, as the reader can verify. However,

the next prime is n = 11, and 211 ’ 1 = 2047 = 23 · 89 is not prime.

We say that n = 11 is a counterexample to the (proposed) implication in

Example 5. Note that it is enough to ¬nd even one example in which an impli-

cation is not valid to show that the implication is false. Hence it is in a sense

easier to disprove an implication than to prove it.

The implications in Examples 4 and 5 are closely related. They have the form

p ’ q and q ’ p, respectively, where p is the statement “2n ’ 1 is a prime”

and q is the statement “n is a prime.” In general, each of the statements p ’ q

and q ’ p is called the converse of the other, and these examples show that an

implication can be valid even though its converse is not valid.

If both p ’ q and q ’ p are valid, we say that p and q are logically equiv-

alent. We write this as

p ” q,

and read it as “p if and only if q.” Many of the most satisfying theorems assert

that two statements, ostensibly quite different, are in fact logically equivalent.

Example 6. If n is an integer, show that “n is odd” ” “n2 is odd.”

Proof. The proof that “n is odd” ’ “n2 is odd” is given in Example 1. If

n2 is odd, suppose that n is not odd. Then n is even, say n = 2k, where k is

an integer. But then n2 = 2(2k) is even, a contradiction. Hence the implication

q ’ p has been proved by contradiction.

Every mathematics book is full of examples of proofs of implications. This

is because of the importance of the axiomatic method. This procedure arises as

follows: In the course of studying various examples, it is observed that they all

have certain properties in common. This leads to the study of a general, abstract

system where these common properties are assumed to hold. The properties are

then called axioms in the abstract system, and the mathematician proceeds by

deducing other properties (called theorems) from these axioms using the methods

introduced in this appendix. These theorems are then true in all the concrete

examples because the axioms hold in each case. The body of theorems is called

a mathematical theory, and many of the greatest mathematical achievements

take this form. Two of the best examples are number theory and group theory,

which derive a wealth of theorems from 5 and 4 axioms, respectively.

The axiomatic method is not new: Euclid ¬rst used it in about 300 B.C.E. to

derive all the propositions of (euclidean) geometry from a list of 10 axioms. His

book, The Elements, is one of the enduring masterpieces of mathematics.

Appendix 2

INTEGERS

The set Z = {0, ±1, ±2, ±3, . . .} of integers is essential to all of algebra, and

has been studied for centuries. In this short section we derive the basic properties

of Z, focusing on the idea of the greatest common divisor, and culminating in

the prime factorization theorem. We assume a basic knowledge of the addition

and multiplication of integers, and of their ordering.

INDUCTION

The following principle is an axiom for the set P = {1, 2, . . .} of positive num-

bers.

Well-Ordering Axiom. Every nonempty subset of P has a smallest member.

Our ¬rst deduction from the axiom gives a very useful method for proving

sequences of statements are true.

Theorem 1. Induction Principle. Let p1 , p2 , . . . be statements such that:

(i) p1 is true.

(ii) If pk is true for some value of k 1, then pk+1 is true.

Then pn is true for every n 1.

Proof. Let X = {n 1|pn is false}. If X is nonempty, let m denote the small-

est member of X (by the well-ordering axiom). Then m = 1 by (i), so if we write

n = m ’ 1, then n 1 and pn is true because n ∈ X. But then pm = pn+1 is true

/

by (ii), a contradiction. So X is empty, as required.

Example 2. Prove Gauss™ formula: 1 + 2 + · · · + n = 1 n(n + 1) for n 1.

2

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

296

INTEGERS 297

Proof. If pn denotes the statement 1 + 2 + · · · + n = 1 n(n + 1) then p1 is

2

true. If pk holds, pk+1 is true because 1 + 2 + · · · + k + (k + 1) = 1 k(k + 1) +

2

(k + 1) = 2 (k + 1)(k + 2). Hence every pk is true by the induction principle.

1

There is nothing special about 1 in the induction principle. In fact, the list of

statements can be started from any integer b.

Corollary 3. Extended Induction. If b is an integer, let pb , pb+1 , . . . be state-

ments such that:

(i) pb is true.

(ii) If pk is true for some value of k b, then pk+1 is true.

Then pn is true for every n b.

Proof. Apply the induction principle to show that the statements q1 , q2 , . . .

are all true, where qk is the statement that “pb+k’1 is true.” This means that

pb , pb+1 , . . . are all true, as desired.

Sometimes it is convenient to be able to replace the inductive assumption

that “pk is true” in Corollary 3 (ii) with the stronger assumption that “each of

pb , pb+1 , . . . , pk is true.” This is valid by the next theorem.

Theorem 4. Strong Induction. If b is an integer, let pb , pb+1 , . . . be statements

such that:

(i) pb is true.

(ii) If pb , pb+1 , . . . , pk are all true for some value of k b then pk+1 is true.

Then pn is true for every n b.

Proof. Apply extended induction to the new statements qb , qb+1 , . . ., where

qk is the statement that “each of pb , pb+1 , . . . , pk is true.”

An integer p is called a prime if p 2 and p cannot be written as a product

of positive integers apart from p = 1 · p. Hence the ¬rst few primes are 2, 3, 5,

7, 11, 13, . . .. With a little experimentation, you can convince yourself that every

integer n 2 is a product of (one or more) primes. Strong induction is needed

to prove it.

Theorem 5. Every integer n 2 is a product of primes.

Proof. Let pn denote the statement of the theorem. Then p2 is clearly true.

If p2 , p3 , . . . , pk are all true, consider the integer k + 1. If k + 1 is a prime,

there is nothing to prove. Otherwise, k + 1 = ab, where 2 a, b k. But then

each of a and b are products of primes because pa and pb are both true by the

(strong) induction assumption. Hence ab = k + 1 is also a product of primes, as

required.

298 INTEGERS

Corollary 6. Euclid™s Theorem. There are in¬nitely many primes.

Proof. Suppose on the contrary that p1 , p2 , . . . , pm are all the primes. In

that case, consider the integer n = 1 + p1 p2 · · · pm . It is a product of primes by

Theorem 5, so is a multiple of pi for some i = 1, 2, . . . , m. But then 1 is an

integral multiple of pi , a contradiction.

Another famous question concerns twin primes, that is, consecutive odd num-

bers that are both primes: 3 and 5, 5 and 7, 11 and 13, . . .. The question is

whether there are in¬nitely many twin primes. One curious fact which suggests

1

that there may be only ¬nitely many is that the series p a twin prime of

p

1

reciprocals of twin primes is convergent, whereas the series p a prime

p

of all prime reciprocals is known to be divergent. But the question remains open.

Euclid™s theorem certainly implies that there are in¬nitely many odd primes,

that is, primes of the form 2k + 1, where k 1. A natural question is whether

if a and b are positive integers, there are in¬nitely many primes of the form

ak + b, k 1. This clearly cannot happen if a and b are both multiples of some

integer greater than 1. But it is true if 1 is the only positive common divisor of

a and b, a famous theorem ¬rst proved by P. G. L. Dirichlet (1805“1859).

DIVISORS

When we write fractions like 22 1 we are using the fact that 22 = 3 · 7 + 1; that

7

is, when 22 is divided by 7 there is a remainder of 1. The general form of this

observation is fundamental to the study of Z.

Theorem 7. Division Algorithm— . Let n and d 1 be integers. There exist

uniquely determined integers q and r such that

n = qd + r and 0 r < d.

Proof. Let X = {n ’ td|t ∈ Z, n ’ td 0}. Then X is nonempty (if n 0,

then n ∈ X; if n < 0, then n(1 ’ d) ∈ X). Hence let r be the smallest member

of X (by the well-ordering axiom). Then r = n ’ qd for some q ∈ Z, and it

remains to show that r < d. But if r d, then 0 r ’ d = n ’ (q + 1)d, so

r ’ d is in X contrary to the minimality of r.

As to uniqueness, suppose that n = q d + r , where 0 r < d. We may

r). Then 0 r ’ r =

assume that r r (a similar argument works if r

(q ’ q)d, so (q ’ q)d is a nonnegative multiple of d that is less than d (because

r ’ r r < d). The only possibility is (q ’ q)d = 0, so q = q, and hence

r = r.

—

This as not an algorithm at all, it is a theorem, but the name is well established.

INTEGERS 299

Given n and d 1, the integers q and r in Theorem 7 are called, respectively,

the quotient and remainder when n is divided by d. For example, if we divide

n = ’29 by d = 7, we ¬nd that ’29 = (’5) · 7 + 6, so the quotient is ’5 and

remainder is 6.

The usual process of long division is a procedure for ¬nding the quotient and

remainder for a given n and d 1. However, they can easily be found with a

n

calculator. For example, if n = 3196 and d = 271 then = 11.79 approximately,

d

so q = 11. Then r = n ’ qd = 215, so 3196 = 11 · 271 + 215, as desired.

If d and n are integers, we say that d divides n, or that d is a divisor of n, if

n = qd for some integer q. We write d|n when this is the case. Thus, a positive

integer p is prime if and only if p has no positive divisors except 1 and p. The

following properties of the divisibility relation | are easily veri¬ed:

(i) n|n for every n.

(ii) If d|m and m|n, then d|n.

If d|n and n|d, then d = ±n.

(iii)

If d|n and d|m, then d|(xm + yn) for all integers x and y.

(iv)

These facts will be used frequently below (usually without comment).

Given positive integers m and n, an integer d is called a common divisor of

m and n if d|m and d|n. The set of common divisors of m and n clearly has

a maximum element; what is surprising is that this largest common divisor is

actually a multiple of every common divisor. With this in mind, we make the

following de¬nition: If m and n are integers, not both zero, we say that d is the

greatest common divisor of m and n, and write d = gcd(m, n), if the following

three conditions are satis¬ed:

(i) d 1.

(ii) d|m and d|n.

(iii) If k|m and k|n, then k|d.

In other words, d = gcd(m, n) is a positive common divisor that is a multiple of

every common divisor. It is routine to use conditions (i) to (iii) to show that d

is unique if it exists. Note that d does not exist if m = 0 = n, but it does exist

in every other case (although this is not apparent). In fact, even more is true:

Theorem 8. Let m and n be integers, not both zero. Then d = gcd(m, n) exists,

and d = xm + yn for some integers x and y.

Proof. Let X = {sm + tn|s, t ∈ Z; sm + tn 1}. Then X is not empty since

m + n2 is in X, so let d be the smallest member of X (by the well-ordering

2

axiom). Since d ∈ X we have d 1 and d = xm + ym for integers x and y, prov-

ing conditions (i) and (iii) in the de¬nition of the gcd. Hence it remains to show

that d|m and d|n. We show that d|n; the other is similar. By the division algorithm

300 INTEGERS

write n = qd + r, where 0 r < d. Then r = n ’ q(xm + yn) = (’qx)m +

(1 ’ qy)n. Hence, if r 1, then r ∈ X, contrary to the minimality of d. So

r = 0 and we have d|n.

When gcd(m, n) = xm + yn where x and y are integers, we say that gcd(m, n)

is a linear combination of m and n. There is an ef¬cient way of computing x and

y using the division algorithm. The following example illustrates the method.

Example 9. Find gcd(37, 8) and express it as a linear combination of 37 and 8.

Proof. It is clear that gcd(37, 8) = 1 because 37 is a prime; however, no linear

combination is apparent. Dividing 37 by 8, and then dividing each successive

divisor by the preceding remainder, gives the ¬rst set of equations. The last

37 = 4 · 8 + 5 1 = 3 ’ 1 · 2 = 3 ’ 1(5 ’ 1 · 3)

8=1·5+3 = 2 · 3 ’ 5 = 2(8 ’ 1 · 5) ’ 5

5=1·3+2 = 2 · 8 ’ 3 · 5 = 2 · 8 ’ 3(37 ’ 4 · 8)

3=1·2+1 = 14 · 8 ’ 3 · 37

2=2·1

nonzero remainder is 1, the greatest common divisor, and this turns out always

to be the case. Eliminating remainders from the bottom up (as in the second set

of equations) gives 1 = 14 · 8 ’ 3 · 37.

The method in Example 9 works in general.

Theorem 10. Euclidean Algorithm. Given integers m and n 1, use the divi-

sion algorithm repeatedly:

m = q1 n + r1 0 r1 < n

n = q2 r1 + r2 0 r2 < r1

r1 = q3 r2 + r3 0 r3 < r2

. .

. .

. .

rk’2 = qk rk’1 + rk 0 rk < rk’1

rk’1 = qk+1 rk

where in each equation the divisor at the preceding stage is divided by the

remainder. These remainders decrease

r1 > r2 > · · · 0

INTEGERS 301

so the process eventually stops when the remainder becomes zero. If r1 = 0,

then gcd(m, n) = n. Otherwise, rk = gcd(m, n), where rk is the last nonzero

remainder and can be expressed as a linear combination of m and n by eliminat-

ing remainders.

Proof. Express rk as a linear combination of m and n by eliminating remain-

ders in the equations from the second last equation up. Hence every common

divisor of m and n divides rk . But rk is itself a common divisor of m and n (it

divides every ri ”work up through the equations). Hence rk = gcd(m, n).

Two integers m and n are called relatively prime if gcd(m, n) = 1. Hence

12 and 35 are relatively prime, but this is not true for 12 and 15 because

gcd(12, 15) = 3. Note that 1 is relatively prime to every integer m. The following

theorem collects three basic properties of relatively prime integers.

Theorem 11. If m and n are integers, not both zero:

(i) m and n are relatively prime if and only if 1 = xm + yn for some integers

x and y.

m n

(ii) If d = gcd(m, n), then and are relatively prime.

d d

(iii) Suppose that m and n are relatively prime.

(a) If m|k and n|k, where k ∈ Z, then mn|k.

(b) If m|kn for some k ∈ Z, then m|k.

Proof. (i) If 1 = xm + yn with x, y ∈ Z, then every divisor of both m and n

divides 1, so must be 1 or ’1. It follows that gcd(m, n) = 1. The converse is by

the euclidean algorithm.

m n

(ii). By Theorem 8, write d = xm + yn, where x, y ∈ Z. Then 1 = x + y ,

d d

and (ii) follows from (i).

(iii). Write 1 = xm + yn, where x, y ∈ Z. If k = am and k = bn, a, b ∈ Z,

then k = kxm + kyn = (xb + ya)mn, and (a) follows. As to (b), suppose that

kn = qm, q ∈ Z. Then k = kxm + kyn = (kx + qn)m, so m|k.

PRIME FACTORIZATION

Recall that an integer p is called a prime if:

(i) p 2.

(ii) The only positive divisors of p are 1 and p.

The reason for not regarding 1 as a prime is that we want the factorization of

every integer into primes (as in Theorem 5) to be unique. The following result

is needed.

302 INTEGERS

Theorem 12. Euclid™s Lemma. Let p denote a prime.

(i) If p|mn where m, n ∈ Z, then either p|m or p|n.

(ii) If p|m1 m2 · · · mr where each mi ∈ Z, then p|mi for some i.

Proof. (i) Write d = gcd(m, p). Then d|p, so as p is a prime, either d =

p or d = 1. If d = p, then p|m; if d = 1, then since p|mn, we have p|n by

Theorem 11.

(ii) This follows from (i) using induction on r.

By Theorem 5, every integer n 2 can be written as a product of (one or

more) primes. For example, 12 = 22 · 3, 15 = 3 · 5, 225 = 32 · 52 . This factoriza-

tion is unique.

Theorem 13. Prime Factorization Theorem. Every integer n 2 can be writ-

ten as a product of (one or more) primes. Moreover, this factorization is unique

except for the order of the factors. That is, if

n = p1 p2 · · · pr and n = q1 q2 · · · qs ,

where the pi and qj are primes, then r = s and the qj can be relabeled so that

pi = qi for each i.

Proof. The existence of such a factorization was shown in Theorem 5. To

prove uniqueness, we induct on the minimum of r and s. If this is 1, then n is

a prime and the uniqueness follows from Euclid™s lemma. Otherwise, r 2 and

s 2. Since p1 |n = q1 q2 · · · qs Euclid™s lemma shows that p1 divides some qj ,

say p1 |q1 (after possible relabeling of the qj ). But then p1 = q1 because q1 is

a prime. Hence p1 = p2 p3 · · · pr = q2 q3 · · · qs , so, by induction, r ’ 1 = s ’ 1

n

and q2 , q3 , . . . , qs can be relabeled such that pi = qi for all i = 2, 3, . . . , r. The

theorem follows.

It follows that every integer n 2 can be written in the form

nn

n = p1 1 p2 2 · · · pr r ,

n

where p1 , p2 , . . . , pr are distinct primes, ni 1 for each i, and the pi and ni are

determined uniquely by n. If every ni = 1, we say that n is square-free, while

if n has only one prime divisor, we call n a prime power.

If the prime factorization n = p1 1 p2 2 · · · pr r of an integer n is given, and if d

nn n

is a positive divisor of n, then these pi are the only possible prime divisors of d

(by Euclid™s lemma). It follows that

Corollary 14. If the prime factorization of n is n = p1 1 p2 2 · · · pr r , then the pos-

nn n

itive divisors d of n are given as follows:

d = p1 1 p2 2 · · · pr r

dd d

where 0 for each i.

di ni

INTEGERS 303

This gives another characterization of the greatest common divisor of two

positive integers m and n. In fact, let p1 , p2 , . . . , pr denote the distinct primes

that divide one or the other of m and n. If we allow zero exponents, these numbers

can be written in the form

nn

n = p1 1 p2 2 · · · pr r

n

0

ni

m = p1 1 p2 2 · · · pr r

mm m

0.

mi

It follows from Corollary 14 that the positive common divisors d of m and n

have the form

dd

d = p1 1 p2 2 · · · pr r

d

where 0 di min(mi , ni ) for each i. [Here min(mi , ni ) denotes the smaller

of the integers mi and ni .] Clearly then, we obtain gcd(m, n) if we set di =

min(mi , ni ) for each i. Before recording this observation (in Theorem 15 below),

we ¬rst consider a natural question: What if we use max(mi , ni ) for each expo-

nent? [Here max(mi , ni ) is the larger of the integers mi and ni .] This leads to

the dual of the notion of a greatest common divisor.

If m and n are positive integers, write n = p1 1 p2 2 · · · pr r and m =

nn n

p1 1 p2 2 · · · pr r where, as before, the pi are distinct primes and we have mi 0

mm m

and ni 0 for each i. We de¬ne the least common multiple of m and n, denoted

lcm(m, n), by

max(m1 ,n1 ) max(m2 ,n2 )

lcm(m, n) = p1 · · · pr

max(mr ,nr )

p2 .

It is clear by Corollary 14 that lcm(m, n) is a common multiple of m and n,

and that it is a divisor of any such common multiple. Hence lcm(m, n) is indeed

playing a role dual to that of the greatest common divisor. This discussion is

summarized in

Theorem 15. Suppose that m and n are positive integers, and write

nn

n = p1 1 p2 2 · · · pr r

n

0

ni

m = p1 1 p2 2 · · · pr r

mm m

0,

mi

where the pi are distinct primes. Then:

min(m1 ,n1 ) min(m2 ,n2 )

gcd(m, n) = p1 · · · pr

min(mr ,nr )

p2

max(m1 ,n1 ) max(m2 ,n2 )

lcm(m, n) = p1 · · · pr

max(mr ,nr )

p2 .

The fact that max(m, n) + min(m, n) = m + n for any integers m and n gives

immediately:

Corollary 16. mn = gcd(m, n)lcm(m, n) for all positive integers m and n.

304 INTEGERS

Example 17. Find gcd(600, 294) and lcm(600, 294).

Proof. We have 600 = 23 · 3 · 52 and 294 = 3 · 2 · 72 so, as above, write

600 = 23 31 52 70

294 = 21 31 50 72 .

Then gcd(600, 294) = 21 31 50 70 = 6, while lcm(600, 294) = 23 31 52 72 = 29,400.

Note that Corollary 16 is veri¬ed by the fact that 600 · 294 = 6 · 29,400.

Of course, using Theorem 15 requires ¬nding the prime factorizations of the

integers m and n, and that is not easy. One useful observation is that if n 2 is

√

not a √

prime, then it has a prime factor p n (it cannot have two factors greater

than n), so when looking for prime divisors of n it is only necessary to test

√

the primes p n. But for large integers, this is dif¬cult, if not impossible. The

euclidean algorithm (and Corollary 16) is a better method for ¬nding greatest

common divisors and least common multiples.

Note that this all generalizes: Given a ¬nite collection a, b, c, . . . of positive

integers, write them as

aa

a = p1 1 p2 2 · · · pr r

a

0

ai

b = p1 1 p2 2 · · · pr r

bb b

0

bi

c = p11 p22 · · · pr r

cc c

0,

ci

. .

. .

. .

where the pi are the distinct primes that divide at least one of a, b, c, . . .. Then

de¬ne their greatest common divisor and least common multiple as follows:

min(a min(a

gcd(a, b, c, . . .) = p1 1 ,b1 ,c1 ,···) p2 2 ,b2 ,c2 ,···) · · · pr r ,br ,cr ,···)

min(a

max(a max(a

lcm(a, b, c, . . .) = p1 1 ,b1 ,c1 ,···) p2 2 ,b2 ,c2 ,···) · · · pr

max(ar ,br ,cr ,···)

.

Then Theorem 15 extends as follows: gcd(a, b, c, . . .) is the common divisor of

a, b, c, . . ., that is, a multiple of every such common divisor, and lcm(a, b, c, . . .)

is the common multiple of a, b, c, . . ., that is, a divisor of every such com-

mon multiple.

This is as far as we go into number theory, the study of the integers, a subject

that has fascinated mathematicians for centuries. There remain many unanswered

questions, among them the celebrated Goldbach conjecture that every even

number greater than 2 is the sum of two primes. This appears to be very dif¬cult,

but it is known that every suf¬ciently large even number is the sum of a prime

and a number that is the product of at most two primes.

However, the twentieth century brought one resounding success. The fact that

3 + 42 = 52 shows that the equation a k + bk = ck has integer solutions if k = 2.

2

INTEGERS 305

However, Fermat asserted that there are no positive integer solutions if k 3. He

wrote a note in his copy of Arithmetica by Diophantus that “I have discovered

a truly remarkable proof but the margin is to small to contain it.” The result

became known as Fermat™s last theorem and remained open for 300 years. But

in 1997, Andrew Wiles proved the result: He related Fermat™s conjecture to a

problem in geometry, which he solved.

BIBLIOGRAPHY AND

REFERENCES

Proofs in Mathematics

1. Bloch, Ethan D., Proofs and Fundamentals: A First Course in Abstract Mathematics. Boston:

Birkhauser, 2000.

2. Schumacher, Carol, Chapter Zero: Fundamental Notions of Abstract Mathematics, 2nd ed. Read-

ing, Mass.: Addison-Wesley, 2000.

3. Solow, Daniel, How to Read and Do Proofs: An Introduction to Mathematical Thought Pro-

cesses, 3rd ed. New York: Wiley, 2002.

Modern Algebra in General

4. Artin, Michael, Algebra. Upper Saddle River, N.J.: Prentice Hall, 1991.

5. Birkhoff, Garrett, and Thomas C. Bartee, Modern Applied Algebra. New York: McGraw-Hill,

1970.

6. Birkhoff, Garrett, and Saunders Maclane, A Survey of Modern Algebra, 4th ed. New York:

Macmillan, 1977.

7. Durbin, John R., Modern Algebra: An Introduction, 4th ed. New York: Wiley, 2000.

8. Gallian, Joseph A., Contemporary Abstract Algebra, 5th ed. Boston: Houghton Mif¬‚in, 2002.

9. Herstein, I. N., Topics in Algebra, 2nd ed. New York: Wiley, 1973.

10. Lidl, Rudolf, and Gunter Pilz, Applied Abstract Algebra, 2nd ed. New York: Springer-Verlag,

1997.

11. Nicholson, W. Keith, Introduction to Abstract Algebra, 2nd ed. New York: Wiley, 1999.

12. Weiss, Edwin, First Course in Algebra and Number Theory. San Diego, Calif.: Academic Press,

1971.

History of Modern Algebra

13. Kline, Morris, Mathematical Thought from Ancient to Modern Times, Vol. 3. New York: Oxford

University Press, 1990 (Chap. 49).

14. Stillwell, John, Mathematics and Its History, 2nd ed. New York: Springer-Verlag, 2002.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

306

BIBLIOGRAPHY AND REFERENCES 307

Connections to Computer Science and Combinatorics

15. Biggs, Norman L., Discrete Mathematics, 2nd ed. Oxford: Oxford University Press, 2003.

16. Davey, B. A., and H. A. Priestley, Introduction to Lattices and Order, 2nd ed. Cambridge:

Cambridge University Press, 2002.

17. Gathen, Joachim von zur, and J¨ rgen Gerhard, Modern Computer Algebra, 2nd ed. Cambridge:

u

Cambridge University Press, 2003.

18. Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory,

Languages, and Computation, 2nd ed. Reading, Mass.: Addison-Wesley, 2000.

19. Knuth, Donald E., The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 3rd

ed. Reading, Mass.: Addison-Wesley, 1998.

20. Kolman, Bernard, Robert C. Busby, and Sharon Cutler Ross, Discrete Mathematical Structures,

4th ed. Upper Saddle River, N.J.: Prentice Hall, 1999.

21. Mendelson, Elliott, Schaum™s Outline of Theory and Problems of Boolean Algebra and Switching

Circuits. New York: McGraw-Hill, 1970.

22. Stone, Harold S., Discrete Mathematical Structures and Their Applications. Chicago: Science

Research Associates, 1973.

23. Whitesitt, J. Eldon, Boolean Algebra and Its Applications. New York: Dover, 1995.

Groups and Symmetry

24. Armstrong, Mark Anthony, Groups and Symmetry. New York: Springer-Verlag, 1988.

25. Baumslag, Benjamin, and Bruce Chandler, Schaum™s Outline of Group Theory. New York:

McGraw-Hill, 1968.

26. Budden, F. J., The Fascination of Groups. Cambridge: Cambridge University Press, 1972.

27. Coxeter, H. S. M., Introduction to Geometry, 2nd ed. New York: Wiley, 1989.

28. Cundy, H. Martyn, and A. P. Rollett, Mathematical Models, 3rd ed. Stradbroke, Norfolk, Eng-

land: Tarquin, 1981.

29. Field, Michael, and Martin Golubitsky, Symmetry in Chaos: A Search for Pattern in Mathemat-

ics, Art and Nature. Oxford: Oxford University Press, 1992.

30. Hall, Marshall, Jr., The Theory of Groups. New York: Macmillan, 1959 (reprinted by the Amer-

ican Mathematical Society, 1999).

31. Lomont, John S., Applications of Finite Groups. New York: Dover, 1993.

32. Shapiro, Louis W., Finite groups acting on sets with applications. Mathematics Magazine, 46

(1973), 136“147.

Rings and Fields

33. Cohn, P. M., Introduction to Ring Theory. New York: Springer-Verlag, 2000.

34. Lidl, Rudolf, and Harald Niederreiter, Introduction to Finite Fields and Their Applications, rev.

ed. Cambridge: Cambridge University Press, 1994.

35. Stewart, Ian, Galois Theory, 3rd ed. Boca Raton, Fla.: CRC Press, 2003.

Convolution Fractions

36. Erdelyi, Arthur, Operational Calculus and Generalized Functions. New York: Holt, Rinehart

and Winston, 1962.

37. Marchand, Jean Paul, Distributions: An Outline. Amsterdam: North-Holland, 1962.

Latin Squares

38. Ball, W. W. Rouse, and H. S. M. Coxeter, Mathematical Recreations and Essays. New York:

Dover, 1987.

308 BIBLIOGRAPHY AND REFERENCES

39. Lam, C. W. H., The search for a ¬nite projective plane of order 10. American Mathematical

Monthly, 98(1991), 305“318.

40. Laywine, Charles F., and Gary L. Mullen, Discrete Mathematics Using Latin Squares. New

York: Wiley, 1998.

Geometrical Constructions

41. Courant, Richard, Herbert Robbins, and Ian Stewart, What Is Mathematics? New York: Oxford

University Press, 1996.

42. Kalmanson, Kenneth, A familiar constructibility criterion. American Mathematical Monthly,

79(1972), 277“278.

43. Kazarinoff, Nicholas D., Ruler and the Round. New York: Dover, 2003.

44. Klein, Felix, Famous Problems of Elementary Geometry. New York: Dover, 1956.

Coding Theory

45. Kirtland, Joseph, Identi¬cation Numbers and Check Digit Schemes. Washington, D.C.: Mathe-

matical Association of America, 2001.

46. Roman, Steven, Introduction to Coding and Information Theory. New York: Springer-Verlag,

1997.

ANSWERS TO THE

ODD-NUMBERED

EXERCISES

CHAPTER 2

2.3. When A © (B C) = ….

2.1. Always true.

2.5. When A © (B C) = ….

2.13. |A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| ’ |A © B|

’|A © C| ’ |A © D| ’ |B © C| ’ |B © D| ’ |C © D|

+|A © B © C| + |A © B © D| + |A © C © D| + |B © C © D|

’|A © B © C © D|.

2.15. 4. 2.17. Yes; P (…).

2.25.

(a) (b) (c) (d)

A B

T T T T T T

T F F F T T

F T T T F F

F F T T T T

(a) and (b) are equivalent and (c) and (d) are equivalent.

2.27. (a) is a contradiction and (b), (c) and (d) are tautologies.

2.29.

B

A C′

B′ C′

D

B′

2.31. B § C .

2.33. A ∨ (B § A ); (A § B) ∨ (A § B ) ∨ (A § B); A ∨ B.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

309

310 ANSWERS TO THE ODD-NUMBERED EXERCISES

2.35. (A ∨ B) § (A ∨ B) § (A ∨ B ); A § B; A § B.

2.39.

D U

D′ U′

2.41. (A § (B ∨ C)) ∨ (B § C). 2.43. (A § B) ∨ (A § B ) ∨ C.

2.45. A ∨ C ∨ D.

2.47. Orange: (A § B § ((C § D) ∨ (C § D ))) ∨ (((A § B) ∨ (A § B )) §

C § D ). Green: A § B § C § D.

2.49. Let the result of multiplying AB by CD be EF. Then the circuit for E

is (A § B § C) ∨ (A § ((B ∨ C ) § D) ∨ (B § C § D )), and the circuit

for F is ((A § C) ∨ (B § D)) § (A ∨ B ∨ C ∨ D ).

2.51. (A ∨ B) § (A ∨ B ); (A ∨ B) § (A ∨ B ) § (A ∨ B ).

2.53. 2.55. 2.57. 60

12 8

4 6 4

30

2

2

6 10

Boolean algebra

1 2

Lattice 3 5

1

Lattice

2.59. The primes pi .

2.67. d = a § b § c .

2.65. Yes.

CHAPTER 3

3.1.

· g2 g3 g4

e g

g2 g3 g4

e e g

g2 g3 g4

g g e

g2 g2 g3 g4 e g

g3 g3 g4 g2

e g

g4 g4 g2 g3

e g

3.3. See Table 8.3.

3.5. Abelian group. 3.7. Abelian group.

3.9. Not a group; the operation is not closed.

3.11. Abelian group. 3.13. Abelian group.

3.15. Group. 3.25. No.

3.27. D2 . 3.29. D6 .

3.31. C6 .

3.33. This is the group O(2) we meet in Chapter 5.

Z, generated by a glide re¬‚ection.

3.35.

ANSWERS TO THE ODD-NUMBERED EXERCISES 311

3.37. C6

e, g 3 e, g 2, g 4

e

3.39. No.

For any c ∈ Q, f : Z ’ Q de¬ned by f (n) = cn for all n ∈ Z.

3.41.

No; Q— has an element of order 2, whereas Z does not.

3.43.

3.45. The identity has order 1; (12) Ž (34), (13) Ž (24), (14) Ž (23) have order 2,

and all the other elements have order 3.

3.47.

· ’1 ’i ’j ’k

1 i j k

’1 ’i ’j ’k

1 1 i j k

’1 ’1 ’i ’j ’k

1 i j k

’i ’1 ’k ’j

1

i i k j

’i ’i ’1 ’k ’j

1

i k j

’j ’k ’1 ’i

1

j j k i

’j ’j ’k ’1 ’i

1

j k i

’k ’j ’i ’1 1

k k j i

’k ’k ’j ’i ’1

1

k j i

The identity, 1, has order 1; ’1 has order 2; all the other elements have

order 4.

1234

3.53. {(1), (123), (132)}. 3.55. .

1342

3.57. (12435).

3.59. (165432) is of order 6 and is odd.

3.61. (1526) Ž (34) is of order 4 and is even.

12345

3.63. . 3.65. (132).

23451

3.67. {(1), (12), (34), (12) Ž (34), (13) Ž (24), (14) Ž (23), (1324), (1423)}.

3.69. {(1), (13), (24), (13) Ž (24), (12) Ž (34), (14) Ž (23), (1234), (1432)}.

3.73. φ(n), the number of positive integers less than n that are relatively prime

to n.

3.77. {e}.

3.75. 52; 8.

3.83. (1) Achievable; (3) achievable.

3.85. S3 . 3.87. S2 .

3.89. F is not abelian; y ’1 x ’1 y ’1 xx.

CHAPTER 4

4.1. Equivalence relation whose equivalence classes are the integers.

4.3. Not an equivalence relation.

312 ANSWERS TO THE ODD-NUMBERED EXERCISES

Left Cosets Right Cosets

4.5.

= {(1), (12), (34), (12) Ž (34)} = {(1), (12), (34), (12) Ž (34)}

H H

= {(13), (123), (134), (1234)} = {(13), (132), (143), (1432)}

(13)H H (13)

= {(14), (124), (143), (1243)} = {(14), (142), (134), (1342)}

(14)H H (14)

= {(23), (132), (234), (1342)} = {(23), (123), (243), (1243)}

(23)H H (23)

= {(24), (142), (243), (1432)} = {(24), (124), (234), (1234)}

(24)H H (24)

= {(1324), (14) Ž (23), = {(1324), (13) Ž (24),

(1324)H H (1324)

(13) Ž (24), (1423)} (14) Ž (23), (1423)}

4.7. Not a morphism.

A morphism; Kerf = 4Z, and Imf = {(0, 0), (1, 1), (0, 2), (1, 3)}.

4.9.

4.11. Not a morphism. 4.19. No.

f : C3 ’ C4 de¬ned by f (g ) = e.

r

4.21.

fk : C6 ’ C6 de¬ned by fk (g r ) = g kr for k = 0, 1, 2, 3, 4, 5.

4.23.

Not isomorphic; C60 contains elements of order 4, whereas C10 — C6

4.25.

does not.

Not isomorphic; Cn — C2 is commutative, whereas Dn is not.

4.27.

√

Not isomorphic; (1 + i)/ 2 has order 8, whereas Z4 — Z2 contains no

4.29.

element of order 8.

4.39. (R+ , ·).

4.33. C10 and D5 .

G2 ∼ S3 .

=

4.49.

5 is a generator of Z— , and 3 is a generator of Z— .

4.59. 6 17

CHAPTER 5

C2 — C2 .

5.1. C2 and C2 . 5.3. C2 and

5.5. C3 and D3 . 5.7. C9 and C9 .

5.9. D4 . 5.11. S4 .

5.13. S4 . 5.15. S4 .

5.17. A5 . 5.19. A5 .

5.21. A5 . 5.25. S4 .

® ®

’1 00 001

° 0 ’1 0 » and ° 1 0 0 ».

5.27.

0 01 010

5.29. D6 . 5.31. C2 .

® ®

’1 0 0 ’1

0 0

5.33. D4 generated by ° 0 1 0 » and ° 1 0 ».

0

0 0 ’1 0 0 1

CHAPTER 6

6.1. 3. 6.3. 38.

6.5. 78. 6.7. 35.

ANSWERS TO THE ODD-NUMBERED EXERCISES 313

(n6 + 3n4 + 8n2 )/12.

6.9. 333. 6.11.

6.13. 1. 6.15. 96.

6.17. 30. 6.19. 396.

6.21. 126. 6.23. 96.

CHAPTER 7

7.1. Monoid with identity 0. 7.3. Semigroup.

7.5. Neither. 7.7. Semigroup.

7.9. Semigroup. 7.11. Monoid with identity 1.

7.13. Neither.

7.15.

gcd 1 2 3 4

1 1 1 1 1

2 1 2 1 2

3 1 1 3 1

4 1 2 1 4

7.17.

· c2 c3 c4

e c

c2 c3 c4

e e c

c2 c3 c4 c2

c c

c2 c2 c3 c4 c2 c3

c3 c3 c4 c2 c3 c4

c4 c4 c2 c3 c4 c2

7.19. No; 01 = 1 in the free semigroup.

7.29. 1

0

0 1 0 1 0 Sends an

s1 s2 s3 s4 s5

output signal

1

1 0

7.31. A congruence relation with quotient semigroup = {2N, 2N + 1}.

7.33. Not a congruence relation.

7.35.

[0] [1] [00] [10] [01] [010]

[0] [00] [01] [0] [010] [1] [10]

[1] [10] [1] [1] [10] [01] [010]

[00] [0] [1] [00] [10] [01] [010]

[10] [1] [01] [10] [010] [1] [10]

[01] [010] [01] [01] [010] [1] [10]

[010] [01] [1] [010] [10] [01] [010]

7.37. 24.

314 ANSWERS TO THE ODD-NUMBERED EXERCISES

7.39.

[] [±] [β] [γ ] [±β] [±γ ]

[] [] [±] [β] [γ ] [±β] [±γ ]

[±] [±] [] [±β] [±γ ] [β] [γ ]

[β] [β] [β] [β] [γ ] [β] [γ ]

[γ ] [γ ] [γ ] [γ ] [β] [γ ] [β]

[±β] [±β] [±β] [±β] [±γ ] [±β] [±γ ]

[±γ ] [±γ ] [±γ ] [±γ ] [±β] [±γ ] [±β]

7.41. 7.43.

0 0

s0 s1 0

0, 1 1 s 00 s 01

1 1

0 0

s 10

s 11

1 1

{[0], [1]}. {[0], [1], [10]}.

7.45. The monoid contains 27 elements.

CF

R W W F

Dormant Dormant Dormant Buds Dead

1 2 3

CF

WCF R R RWC RWCF

CHAPTER 8

8.1. + ·

0 1 2 3 0 1 2 3

0 0 1 2 3 0 0 0 0 0

1 1 2 3 0 1 0 1 2 3

2 2 3 0 1 2 0 2 0 2

3 3 0 1 2 3 0 3 2 1

8.3. A ring.

8.5. Not a ring; not closed under multiplication.

8.7. Not a ring; not closed under addition.

8.9. A ring.

8.11. Not a ring; distributive laws do not hold.

8.17. A subring.

8.19. Not a subring; not closed under addition.

8.21. Neither. 8.23. Both.

8.25. Integral domain. 8.29. [2], [4], [5], [6], [8].

ANSWERS TO THE ODD-NUMBERED EXERCISES 315

8.31. Any nonempty proper subset of X.

8.33. Nonzero matrices with zero determinant.

f (x) = [x]6 .

8.37.

f (x, y) = (x, y), (y, x), (x, x) or (y, y).

8.39.

(b) ’1 and 0.

8.47.

The identity is Dn (x) = (1/2π) + (1/π)(cos x + cos 2x + · · · + cos nx).

8.55.

The ring is not an integral domain.

CHAPTER 9

+ 5 x ’ 15 and 45 x + 7 .

32

9.1. x