<<

. 12
( 13)



>>


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

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

<<

. 12
( 13)



>>