## 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.