A Concrete Introduction to Higher Algebra, Third edition
By Lindsay N. Childs
Contents
Part I Numbers
1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Euclid’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Unique Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Part II Congruence classes and rings
6 Congruence Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8 Matrices and Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Part III Congruences and Groups
9 Fermat’s and Euler’s Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10 Applications of Euler’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
11 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
12 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Part IV Polynomials
13 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
14 Unique Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
15 The Fundamental Theorem of Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
16 Polynomials in Q[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
17 Congruences and the Chinese Remainder Theorem . . . . . . . . . . . . . . . . 355
18 Fast Polynomial Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
Part V Primitive Roots
19 Cyclic Groups and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
20 Carmichael Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
21 Quadratic Reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
22 Quadratic Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Part VI Finite Fields
23 Congruence Classes Modulo a Polynomial . . . . . . . . . . . . . . . . . . . . . . . . 479
24 Homomorphisms and Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
25 BCH Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Part VII Factoring Polynomials
26 Factoring in Z[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
27 Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
Answers and Hints to the Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
Introduction
This book is an introduction to higher algebra for students with a background of a year of calculus. The first edition of this book emerged from a set of notes written in the 1970’s for a sophomore-junior level undergraduate course at the University at Albany entitled “Classical Algebra”. The objective of the course, and the book, is to offer students a highly motivated introduction to the basic concepts of abstract algebra—rings and fields, groups, homomorphisms—by developing the algebraic theory of the familiar examples of integers and polynomials, and introducing the abstract concepts as needed to help illuminate the theory. By building the algebra out of numbers and polynomials, the book takes maximal advantage of the student’s prior experience in algebra and arithmetic from secondary school and calculus. The new concepts of abstract algebra arise in a familiar context.
An ultimate goal of the presentation is to reach a substantial result in abstract algebra, namely, the classification of finite fields. But while heading generally towards that goal, motivation is maintained by many applications of the new concepts. The student can see throughout that the concepts of abstract algebra help illuminate more concrete mathematics, as well as lead to substantial theoretical results. Thus a student who asks, “Why am I learning this?” will find answers usually within a chapter or two. While our course is called “Classical Algebra” and the book begins with mathematics dating from Euclid (300 BC) and before, the book also includes a substantial amount of mathematics discovered only within the past three generations. Thus this book is explicitly offered as a counterexample to Alan Hammond’s (1980) remark that “Mathematics is one of the few subjects that a student can study through high school and even a few years into college without coming into contact with any results invented since 1800.”
The extent and variety of applications in the book have led to the book being used in courses rather different than the course for which it was originally designed. The book has been used for courses in Applied Algebra or Applicable Algebra, in Elementary Number Theory, and in Algebra for Teachers. Possible outlines for such courses are described below.
Notes on the Third Edition
The first and second editions of this book were published in 1979 and 1995, a gratifyingly
long time ago. The second edition was an extensive revision and expansion
(160 pages) of the first edition. This third edition is an extensive revision and somewhat
more modest expansion (around 85 pages) of the second edition.
The new edition is organized into seven parts, as follows:
I. Numbers. Chapters 1-5 present the elementary theory of the integers—induction,
divisibility, Euclid’s Algorithm, unique factorization into prime numbers and congruence
modulo m. These ideas and techniques lay the groundwork for the
mathematics and applications in the remainder of the book. Section 4D begins a
discussion of prime numbers, and Sections 5C and 5D introduce two applications
of congruence to error detection—casting out nines and Luhn’s formula.
II. Congruence classes and rings. Chapter 6 introduces the ring of congruence
classesmodulom, and Chapter 7 introduces some basic concepts of abstract algebrarings,
fields, groups, homomorphisms—that can be used to help identify properties
and features of congruence classes. Chapter 8 reviews elementary ideas of matrices
and linear equations needed for subsequent applications. Applications include
Karatsuba multiplication, the use of modular arithmetic to the design of tournaments
and to factoring by trial division, and the use of matrices with entries in the integers
modulo m to error-correcting codes (Hamming codes) and to cryptography (the Hill
cryptosystem).
III. Congruences and groups. Chapters 9–11 focus on the multiplicative group of
units of the integers modulo m. Chapter 9 obtains Fermat’s and Euler’s Theorems,
with two distinctly different proofs; Chapter 11 develops some finite group theory,
enough to prove Lagrange’s Theorem and to introduce quotient groups. Lagrange’s
Theorem yields a third proof of Fermat’s and Euler’s Theorems. Sections 9E and
9F introduce useful techniques for computing modulo m. Chapter 12 presents the
Chinese Remainder Theorem, an important result in modular arithmetic. The CRT
yields information on the size of groups of units modulo a composite number. Applications
include the connection between Euler’s Theorem and the period of repeating
decimals, and the application of Euler’s Theorem to the famous RSA cryptosystem.
The RSA cryptosystem motivates the search for methods for identifying possible
prime numbers, for factoring large numbers, and for multiplying large numbers.
Approaches to all three problems (pseudoprime testing, the Pollard p−1 method,
using the CRT for multiplying) are presented in Sections 10B, 10C, 11D, and 12C.
IV. Polynomials. Chapters 13–18 introduce the elementary theory of polynomials
in one variable over a field, a theory that closely parallels the theory of the integers
presented in Chapters 2–12—divisibility, Euclid’s Algorithm, unique factorization,
congruence. For integers, prime numbers are the “atoms” that generate all numbers;
in a similar way, irreducible polynomials are the atoms for all polynomials.
So Chapters 15 and 16 are devoted to studying irreducible polynomials and factorization
of polynomials over the rational numbers, the real numbers and the complex
numbers (Fundamental Theorem of Algebra). Chapter 17 introduces congruence for
polynomials and the Chinese Remainder Theorem, which in turn leads to interpolation
and a proof that factoring polynomials over the rational numbers is a finite
process. Chapter 18 presents a fast method of multiplying polynomials, based on
the Chinese Remainder Theorem and a method for evaluating polynomials known
as the Fast Fourier Transform.
V. Primitive Roots. With the availability of D’Alembert’s Theoremin Section 14A,
Chapters 19–22 return to the study of groups of units of integers modulo m.
Chapter 19 introduces enough additional finite group theory (the exponent of an
abelian group, finite cyclic groups) to prove the Primitive Root Theorem. Chapter 21
applies the Primitive Root Theorem and quotient groups from Section 11G to determine
how to decide whether a number is a square modulo m—the famous Law of
Quadratic Reciprocity. These results are applied to cryptography—Diffie-Hellman
key exchange, Blum-Goldwasser cryptography and refinements of RSA cryptography;
to pseudorandom numbers—the linear congruential and Blum-Blum-Shub
methods; and to primality testing and factorization of integers—strong pseudoprimes,
Carmichael numbers and Rabin’s Theorem, the Pollard rho factoringmethod.
VI. Finite Fields. Chapters 23–25 continue the theory for polynomials that parallels
the theory for integers in Chapters 6–7. The construction of congruence classes
for polynomials yields many new fields, fields that can be used to split polynomials
defined over subfields into linear factors. The construction yields a complete classification
of finite fields in Section 24C. Applications of finite fields include Latin
squares (Section 25D) and multiple error-correcting (BCH) codes (Chapter 26).
VII. Factoring Polynomials. Chapters 26 and 27 extend the ideas of Chapters 16
and 17 on factoring polynomials over the rational numbers and integers. Chapter
26 reproves that factoring polynomials over the rationals is a finite process, and
then presents methods to make the process more efficient—Berlekamp’s factoring
algorithmand the Hensel factoringmethod. Chapter 27 extends the ideas of Sections
24B and C to give a count of irreducible polynomials of every degree over the field
of p elements for every prime p, then uses ideas of Section 16B and Chapter 26 to
obtain a result of Van der Waerden that in a certain sense, almost all polynomials
over the rational numbers are irreducible.
Changes in the new edition not already noted include:
- Material on solving equations in the integers and modulo m has been rewritten
and placed in separate sections (3E, 6F).
- The axioms for a field are motivated by looking at how to solve linear equations
(7A).
- There is a greater emphasis on homomorphisms of polynomial rings (starting at
13D)
- The section on congruence modulo a polynomial has been rewritten and expanded
(17A).
- There is more emphasis on the exponent of an abelian group (Chapter 19)
- The section on finite cyclic groups has been rewritten (19B)
- The material on bounding the roots and factors of polynomials with integer coefficients
has been greatly improved (26 A, B).
- There are new sections on cosets and solutions of equations (11E) and on quotient
groups and the “fundamental homomorphismtheorem”,with applications to
groups of units (11G), quadratic reciprocity (21G), and (via Cauchy’s Theorem),
the cardinality of finite fields (24C).
- There is a new application of Eisenstein’s irreducibility criterion to Chebyshev
polynomials (16B)
- There is a new proof of a weak form of Rabin’s Theorem using subgroups and
cosets (20C), and a new proof of quadratic reciprocity (due to G. Rousseau) that
uses the Chinese Remainder Theorem and different coset representatives of a
quotient group (2lC)
In order to keep this edition from getting any larger than it already is, a few sections
found in the second edition have been omitted in the third: the connection
between Euclid’s algorithm and incommensurability, Sturm’s Algorithm, knapsack
cryptosystems, a proof of Rabin’s theorem in its full strength, and Reed-Solomon
codes. This last topic was a close call, but I finally decided that to do Reed-Solomon
well would stray too far from the main objective of the book.
Prerequisites
The explicit prerequisite consists of precalculus algebra. However, long experience
suggests that three or four semesters of college-level mathematics, such as the calculus
sequence and a semester of linear algebra, is helpful. Only a few sections of
the book use calculus or linear algebra. Elementary row operations show up with
the extended Euclidean algorithm in Chapter 3, but otherwise a course can easily
be designed to avoid linear algebra (used in 8E, 8F, 11H, 18, and 25). On the other
hand, if linear algebra is a prerequisite, then a number of the applications can be
done more efficiently.
Designing a course
For an Introduction to Abstract Algebra course that seeks to reach the classification
of finite fields, the theoretical core of the course is found in sections 2B, 3A-E, 4A,
5A-B, E-F, 6A-F, 7A, C-D, 9A-C, 11A-C, E-G, 13, 14, 17A, 19A-B, 23, 24A-C.
For our Classical Algebra course, most instructors do chapters 2, 3A-E, 4, 5, 6A-F,
7A,C,D, 9A-D, 10A, 11A-C,most of 12A-D, 13, 14, 16A,B, 17A, 19A-B, plus other
topics as time allows.
A course in Number Theory could follows chapters 2, 3, 4, 5, 6, 7A, 9, 12, 13A,
14, 20, 21, 22B and 23ABC (plus handouts on special topics of interest to the
instructor).
A course on Applicable Algebra could follow chapters 2, 3, 4, 5, 6, 7ACD, 8E,
9ABC, 10A, 11A-C, E-H, 12ABD, 13, 14, 17ABC, 19AB, 23, 25 (plus supplemental
notes on error-correcting codes).
A course emphasizing polynomials (e.g. for future secondary teachers) could do
chapters 2, 5A-B, 6C, 7A, C, 13–18, 23–27.