MATH 3GR3 Assignment #2Due: Monday, 18 October by 11:59pm

1. Show that if G is an abelian group and a, b ∈ G both have finite order,

then so does the element ab. Find an example of a group G and two

elements a, b ∈ G both of finite order such that ab has infinite order.

2. Find all of the subgroups of Z12 and find all of the generators of this

group.

3. Produce the Cayley table of the group U (12). Is this group cyclic?

4. Let G be a finite cyclic group. Show that if H is a subgroup of G then

|H| divides |G|. Conversely, show that if k is a natural number such

that k divides |G| then there is a subgroup of G of order k.

5. Let H and K be subgroups of the group G. Show that H ∩ K is a

subgroup of G. Show that the subset HK = {h · k : h ∈ H, k ∈ K} is

not necessarily a subgroup, by finding an example that illustrates this.

6. Consider the following two elements of S7 :

1 2 3 4 5 6 7

1 2 3 4 5 6 7

σ=

,τ =

.

6 7 4 3 1 5 2

1 3 4 5 7 6 2

(a) Decompose σ and τ into cycles.

(b) Compute στ and τ σ.

(c) Compute the order of σ, τ , στ , and τ σ.

(d) Determine the signs of σ, τ , στ , and τ σ.

7. What are the possible orders of elements in the group S8 ? For each

one, find an element of that order.

8. Show that every element σ of the group Sn can be written as a product

of transpositions of the form (i, i + 1), where 1 ≤ i < n.
9. Let G be the group of symmetries of the circular disk of radius 1.
Show that G contains elements of every finite order and that it contains
elements of infinite order.
1
Supplementary problems from the textbook
(not to be handed in)
• From Chapter 3, questions 34, 35, 49, 50
• From Chapter 4, questions 1, 2, 3, 10, 23, 24, 25, 30, 39
2
\documentclass[12pt]{article}
\usepackage{amssymb}
\begin{document}
\begin{center}
\large
MATH 3GR3 Assignment \#2
\\
Due: Monday, 18 October by 11:59pm
\end{center}
\begin{enumerate}
\item Show that if $G$ is an abelian group and $a$, $b \in G$ both have finite order, then so
does the element $ab$. Find an example of a group $G$ and two elements $a$, $b \in
G$ both of finite order such that $ab$ has infinite order.
\item Find all of the subgroups of $\mathbb{Z}_{12}$ and find all of the generators of this
group.
\item Produce the Cayley table of the group $U(12)$. Is this group cyclic?
\item Let $G$ be a finite cyclic group. Show that if $H$ is a subgroup of $G$ then
$|H|$ divides $|G|$. Conversely, show that if $k$ is a natural number such that $k$ divides
$|G|$ then there is a subgroup of $G$ of order $k$.
\item Let $H$ and $K$ be subgroups of the group $G$. Show that $H \cap K$ is a subgroup
of $G$. Show that the subset $HK = \{h\cdot k\,:\, h \in H, k \in K\}$ is not necessarily a
subgroup, by finding an example that illustrates this.
\item Consider the following two elements of $S_7$:
\[
\sigma = \left(\begin{array}{ccccccc} 1&2&3&4&5&6&7\\ 6&7&4&3&1&5&2 \end{array}\right),
\tau = \left(\begin{array}{ccccccc} 1&2&3&4&5&6&7\\ 1&3&4&5&7&6&2 \end{array}\right).
\]
\begin{enumerate}
\item Decompose $\sigma$ and $\tau$ into cycles.
\item Compute $\sigma\tau$ and $\tau\sigma$.
\item Compute the order of $\sigma$, $\tau$, $\sigma\tau$, and $\tau\sigma$.
\item Determine the signs of $\sigma$, $\tau$, $\sigma\tau$, and $\tau\sigma$.
\end{enumerate}
\item What are the possible orders of elements in the group $S_8$? For each one, find an
element of that order.
\item Show that every element $\sigma$ of the group $S_n$ can be written as a product of
transpositions of the form $(i, i+1)$, where $1 \le i < n$.
\item Let $G$ be the group of symmetries of the circular disk of radius 1. Show that
$G$ contains elements of every finite order and that it contains elements of infinite order.
\end{enumerate}
\bigskip
\begin{center}
\large
Supplementary problems from the textbook \\
(not to be handed in)
\end{center}
\begin{itemize}
\item From Chapter 3, questions 34, 35, 49, 50
\item From Chapter 4, questions 1, 2, 3, 10, 23, 24, 25, 30, 39
\end{itemize}
\end{document}
Abstract Algebra
Theory and Applications
Abstract Algebra
Theory and Applications
Thomas W. Judson
Stephen F. Austin State University
Sage Exercises for Abstract Algebra
Robert A. Beezer
University of Puget Sound
Traducción al español
Antonio Behn
Universidad de Chile
August 6, 2020
Edition: Annual Edition 2020
Website: abstract.pugetsound.edu
©1997–2020 Thomas W. Judson, Robert A. Beezer
Permission is granted to copy, distribute and/or modify this document under the terms
of the GNU Free Documentation License, Version 1.2 or any later version published by
the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no
Back-Cover Texts. A copy of the license is included in the appendix entitled “GNU Free
Documentation License.”
Acknowledgements
I would like to acknowledge the following reviewers for their helpful comments and suggestions.
• David Anderson, University of Tennessee, Knoxville
• Robert Beezer, University of Puget Sound
• Myron Hood, California Polytechnic State University
• Herbert Kasube, Bradley University
• John Kurtzke, University of Portland
• Inessa Levi, University of Louisville
• Geoffrey Mason, University of California, Santa Cruz
• Bruce Mericle, Mankato State University
• Kimmo Rosenthal, Union College
• Mark Teply, University of Wisconsin
I would also like to thank Steve Quigley, Marnie Pommett, Cathie Griffin, Kelle Karshick,
and the rest of the staff at PWS Publishing for their guidance throughout this project. It
has been a pleasure to work with them.
Robert Beezer encouraged me to make Abstract Algebra: Theory and Applications available as an open source textbook, a decision that I have never regretted. With his assistance,
the book has been rewritten in PreTeXt (pretextbook.org), making it possible to quickly
output print, web, pdf versions and more from the same source. The open source version
of this book has received support from the National Science Foundation (Awards #DUE1020957, #DUE–1625223, and #DUE–1821329).
v
Preface
This text is intended for a one or two-semester undergraduate course in abstract algebra.
Traditionally, these courses have covered the theoretical aspects of groups, rings, and fields.
However, with the development of computing in the last several decades, applications that
involve abstract algebra and discrete mathematics have become increasingly important,
and many science, engineering, and computer science students are now electing to minor in
mathematics. Though theory still occupies a central role in the subject of abstract algebra
and no student should go through such a course without a good notion of what a proof is, the
importance of applications such as coding theory and cryptography has grown significantly.
Until recently most abstract algebra texts included few if any applications. However,
one of the major problems in teaching an abstract algebra course is that for many students it
is their first encounter with an environment that requires them to do rigorous proofs. Such
students often find it hard to see the use of learning to prove theorems and propositions;
applied examples help the instructor provide motivation.
This text contains more material than can possibly be covered in a single semester.
Certainly there is adequate material for a two-semester course, and perhaps more; however,
for a one-semester course it would be quite easy to omit selected chapters and still have a
useful text. The order of presentation of topics is standard: groups, then rings, and finally
fields. Emphasis can be placed either on theory or on applications. A typical one-semester
course might cover groups and rings while briefly touching on field theory, using Chapters 1
through 6, 9, 10, 11, 13 (the first part), 16, 17, 18 (the first part), 20, and 21. Parts of
these chapters could be deleted and applications substituted according to the interests of
the students and the instructor. A two-semester course emphasizing theory might cover
Chapters 1 through 6, 9, 10, 11, 13 through 18, 20, 21, 22 (the first part), and 23. On
the other hand, if applications are to be emphasized, the course might cover Chapters 1
through 14, and 16 through 22. In an applied course, some of the more theoretical results
could be assumed or omitted. A chapter dependency chart appears below. (A broken line
indicates a partial dependency.)
vi
vii
Chapters 1–6
Chapter 8
Chapter 9
Chapter 7
Chapter 10
Chapter 11
Chapter 13
Chapter 16
Chapter 12
Chapter 17
Chapter 18
Chapter 20
Chapter 14
Chapter 15
Chapter 19
Chapter 21
Chapter 22
Chapter 23
Though there are no specific prerequisites for a course in abstract algebra, students
who have had other higher-level courses in mathematics will generally be more prepared
than those who have not, because they will possess a bit more mathematical sophistication.
Occasionally, we shall assume some basic linear algebra; that is, we shall take for granted an
elementary knowledge of matrices and determinants. This should present no great problem,
since most students taking a course in abstract algebra have been introduced to matrices
and determinants elsewhere in their career, if they have not already taken a sophomore or
junior-level course in linear algebra.
Exercise sections are the heart of any mathematics text. An exercise set appears at the
end of each chapter. The nature of the exercises ranges over several categories; computational, conceptual, and theoretical problems are included. A section presenting hints and
solutions to many of the exercises appears at the end of the text. Often in the solutions
a proof is only sketched, and it is up to the student to provide the details. The exercises
range in difficulty from very easy to very challenging. Many of the more substantial problems require careful thought, so the student should not be discouraged if the solution is not
forthcoming after a few minutes of work.
There are additional exercises or computer projects at the ends of many of the chapters.
The computer projects usually require a knowledge of programming. All of these exercises
viii
and projects are more substantial in nature and allow the exploration of new results and
theory.
Sage (sagemath.org) is a free, open source, software system for advanced mathematics,
which is ideal for assisting with a study of abstract algebra. Sage can be used either on
your own computer, a local server, or on CoCalc (cocalc.com). Robert Beezer has written
a comprehensive introduction to Sage and a selection of relevant exercises that appear at
the end of each chapter, including live Sage cells in the web version of the book. All of the
Sage code has been subject to automated tests of accuracy, using the most recent version
available at this time: SageMath Version 9.1 (released 2020-05-20).
Thomas W. Judson
Nacogdoches, Texas 2020
Contents
Acknowledgements
v
Preface
vi
1 Preliminaries
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1
A Short Note on Proofs . . . . .
Sets and Equivalence Relations . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 The Integers
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
22
Mathematical Induction . . . . .
The Division Algorithm . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
Programming Exercises . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Groups
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
1
3
13
14
16
16
21
22
25
28
29
31
31
32
35
37
Integer Equivalence Classes and Symmetries
Definitions and Examples. . . . . . . .
Subgroups . . . . . . . . . . . . . .
Reading Questions . . . . . . . . . .
Exercises . . . . . . . . . . . . . .
Additional Exercises: Detecting Errors . .
References and Suggested Readings . . . .
Sage . . . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . . . .
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
42
47
49
49
52
54
54
60
CONTENTS
x
4 Cyclic Groups
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
62
Cyclic Subgroups . . . . . . . . . . .
Multiplicative Group of Complex Numbers .
The Method of Repeated Squares . . . .
Reading Questions . . . . . . . . . .
Exercises . . . . . . . . . . . . . .
Programming Exercises . . . . . . . .
References and Suggested Readings . . . .
Sage . . . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Permutation Groups
5.1
5.2
5.3
5.4
5.5
5.6
Definitions and Notation
Dihedral Groups . . .
Reading Questions . .
Exercises . . . . . .
Sage . . . . . . . .
Sage Exercises . . . .
85
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 85
. 91
. 96
. 97
. 99
. 106
6 Cosets and Lagrange’s Theorem
6.1
6.2
6.3
6.4
6.5
6.6
6.7
Cosets . . . . . . . . . .
Lagrange’s Theorem . . . . .
Fermat’s and Euler’s Theorems
Reading Questions . . . . .
Exercises . . . . . . . . .
Sage . . . . . . . . . . .
Sage Exercises . . . . . . .
.
.
.
.
.
.
.
108
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Introduction to Cryptography
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
Private Key Cryptography . . . . . . . .
Public Key Cryptography . . . . . . . .
Reading Questions . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . .
Additional Exercises: Primality and Factoring
References and Suggested Readings . . . . .
Sage . . . . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . . . . .
Error-Detecting and Correcting Codes
Linear Codes. . . . . . . . . . .
Parity-Check and Generator Matrices .
Efficient Decoding . . . . . . . .
Reading Questions . . . . . . . .
Exercises . . . . . . . . . . . .
Programming Exercises . . . . . .
References and Suggested Readings . .
Sage . . . . . . . . . . . . . .
108
110
111
112
112
114
117
121
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 Algebraic Coding Theory
8.1
8.2
8.3
8.4
8.5
8.6
8.7
8.8
8.9
62
65
69
71
71
74
74
74
83
121
123
126
127
128
129
130
133
135
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
135
142
145
150
153
153
157
157
158
CONTENTS
xi
8.10 Sage Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 160
9 Isomorphisms
9.1
9.2
9.3
9.4
9.5
9.6
Definition and Examples
Direct Products . . .
Reading Questions . .
Exercises . . . . . .
Sage . . . . . . . .
Sage Exercises . . . .
163
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10 Normal Subgroups and Factor Groups
10.1
10.2
10.3
10.4
10.5
10.6
Factor Groups and Normal Subgroups. .
The Simplicity of the Alternating Group.
Reading Questions . . . . . . . . .
Exercises . . . . . . . . . . . . .
Sage . . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . . .
180
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11 Homomorphisms
11.1
11.2
11.3
11.4
11.5
11.6
11.7
Group Homomorphisms . . . . . .
The Isomorphism Theorems. . . . .
Reading Questions . . . . . . . .
Exercises . . . . . . . . . . . .
Additional Exercises: Automorphisms .
Sage . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . .
Matrix Groups . . . . . . . . .
Symmetry . . . . . . . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Finite Abelian Groups . . . . . .
Solvable Groups . . . . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
Programming Exercises . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
192
194
196
197
198
199
203
205
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13 The Structure of Groups
13.1
13.2
13.3
13.4
13.5
13.6
13.7
13.8
180
182
185
185
187
190
192
12 Matrix Groups and Symmetry
12.1
12.2
12.3
12.4
12.5
12.6
12.7
163
167
170
170
173
178
205
212
218
219
221
221
221
222
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
222
226
229
229
231
231
231
233
CONTENTS
xii
14 Group Actions
14.1
14.2
14.3
14.4
14.5
14.6
14.7
14.8
14.9
234
Groups Acting on Sets . . . . .
The Class Equation . . . . . .
Burnside’s Counting Theorem . .
Reading Questions . . . . . .
Exercises . . . . . . . . . .
Programming Exercise . . . . .
References and Suggested Reading
Sage . . . . . . . . . . . .
Sage Exercises . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15 The Sylow Theorems
15.1
15.2
15.3
15.4
15.5
15.6
15.7
15.8
253
The Sylow Theorems . . . . . .
Examples and Applications . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
A Project . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16 Rings
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17 Polynomials
Polynomial Rings . . . . .
The Division Algorithm . .
Irreducible Polynomials . .
Reading Questions . . . .
Exercises . . . . . . . .
Additional Exercises: Solving
Sage . . . . . . . . . .
Sage Exercises . . . . . .
18 Integral Domains
253
256
258
259
260
261
261
268
270
16.1 Rings. . . . . . . . . . . . .
16.2 Integral Domains and Fields . . .
16.3 Ring Homomorphisms and Ideals. .
16.4 Maximal and Prime Ideals . . . .
16.5 An Application to Software Design .
16.6 Reading Questions . . . . . . .
16.7 Exercises . . . . . . . . . . .
16.8 Programming Exercise . . . . . .
16.9 References and Suggested Readings .
16.10Sage . . . . . . . . . . . . .
16.11Sage Exercises . . . . . . . . .
17.1
17.2
17.3
17.4
17.5
17.6
17.7
17.8
234
236
238
244
244
246
247
247
251
270
273
275
278
280
283
284
287
288
288
297
299
. . . .
. . . .
. . . .
. . . .
. . . .
the Cubic
. . . .
. . . .
. .
. .
. .
. .
. .
and
. .
. .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Quartic Equations
. . . . . . . .
. . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
299
302
305
310
310
312
314
319
321
18.1 Fields of Fractions . . . . . . . . . . . . . . . . . . . . . . . 321
18.2 Factorization in Integral Domains . . . . . . . . . . . . . . . . . 324
18.3 Reading Questions . . . . . . . . . . . . . . . . . . . . . . . 330
CONTENTS
18.4
18.5
18.6
18.7
Exercises . .
References and
Sage . . . .
Sage Exercises
xiii
. . . . . . . . .
Suggested Readings .
. . . . . . . . .
. . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19 Lattices and Boolean Algebras
19.1
19.2
19.3
19.4
19.5
19.6
19.7
19.8
19.9
Lattices . . . . . . . . . . . .
Boolean Algebras . . . . . . . .
The Algebra of Electrical Circuits .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
Programming Exercises . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
337
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20 Vector Spaces
20.1
20.2
20.3
20.4
20.5
20.6
20.7
20.8
Definitions and Examples. . . . .
Subspaces . . . . . . . . . . .
Linear Independence . . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
Extension Fields . . . . . . . .
Splitting Fields . . . . . . . . .
Geometric Constructions . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
358
359
360
362
362
365
365
370
373
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22 Finite Fields
22.1
22.2
22.3
22.4
22.5
22.6
22.7
22.8
337
340
345
347
348
350
350
351
356
358
21 Fields
21.1
21.2
21.3
21.4
21.5
21.6
21.7
21.8
331
333
333
336
Structure of a Finite Field . . . . . .
Polynomial Codes. . . . . . . . . .
Reading Questions . . . . . . . . .
Exercises . . . . . . . . . . . . .
Additional Exercises: Error Correction for
References and Suggested Readings . . .
Sage . . . . . . . . . . . . . . .
Sage Exercises . . . . . . . . . . .
373
381
383
388
388
390
390
398
400
. . . . .
. . . . .
. . . . .
. . . . .
BCH Codes
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
400
404
411
411
413
413
413
415
CONTENTS
xiv
23 Galois Theory
23.1
23.2
23.3
23.4
23.5
23.6
23.7
23.8
Field Automorphisms . . . . . .
The Fundamental Theorem . . . .
Applications . . . . . . . . . .
Reading Questions . . . . . . .
Exercises . . . . . . . . . . .
References and Suggested Readings .
Sage . . . . . . . . . . . . .
Sage Exercises . . . . . . . . .
418
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
418
422
428
432
433
434
435
446
A GNU Free Documentation License
450
B Hints and Answers to Selected Exercises
457
C Notation
471
Index
474
1
Preliminaries
A certain amount of mathematical maturity is necessary to find and study applications
of abstract algebra. A basic knowledge of set theory, mathematical induction, equivalence
relations, and matrices is a must. Even more important is the ability to read and understand
mathematical proofs. In this chapter we will outline the background needed for a course in
abstract algebra.
1.1 A Short Note on Proofs
Abstract mathematics is different from other sciences. In laboratory sciences such as chemistry and physics, scientists perform experiments to discover new principles and verify theories. Although mathematics is often motivated by physical experimentation or by computer
simulations, it is made rigorous through the use of logical arguments. In studying abstract
mathematics, we take what is called an axiomatic approach; that is, we take a collection
of objects S and assume some rules about their structure. These rules are called axioms.
Using the axioms for S, we wish to derive other information about S by using logical arguments. We require that our axioms be consistent; that is, they should not contradict one
another. We also demand that there not be too many axioms. If a system of axioms is too
restrictive, there will be few examples of the mathematical structure.
A statement in logic or mathematics is an assertion that is either true or false. Consider
the following examples:
• 3 + 56 − 13 + 8/2.
• All cats are black.
• 2 + 3 = 5.
• 2x = 6 exactly when x = 4.
• If ax2 + bx + c = 0 and a ̸= 0, then
x=
−b ±
√
b2 − 4ac
.
2a
• x3 − 4x2 + 5x − 6.
All but the first and last examples are statements, and must be either true or false.
A mathematical proof is nothing more than a convincing argument about the accuracy
of a statement. Such an argument should contain enough detail to convince the audience; for
1
CHAPTER 1. PRELIMINARIES
2
instance, we can see that the statement “2x = 6 exactly when x = 4” is false by evaluating
2 · 4 and noting that 6 ̸= 8, an argument that would satisfy anyone. Of course, audiences
may vary widely: proofs can be addressed to another student, to a professor, or to the
reader of a text. If more detail than needed is presented in the proof, then the explanation
will be either long-winded or poorly written. If too much detail is omitted, then the proof
may not be convincing. Again it is important to keep the audience in mind. High school
students require much more detail than do graduate students. A good rule of thumb for an
argument in an introductory abstract algebra course is that it should be written to convince
one’s peers, whether those peers be other students or other readers of the text.
Let us examine different types of statements. A statement could be as simple as “10/5 =
2;” however, mathematicians are usually interested in more complex statements such as “If
p, then q,” where p and q are both statements. If certain statements are known or assumed
to be true, we wish to know what we can say about other statements. Here p is called
the hypothesis and q is known as the conclusion. Consider the following statement: If
ax2 + bx + c = 0 and a ̸= 0, then
√
−b ± b2 − 4ac
.
x=
2a
The hypothesis is ax2 + bx + c = 0 and a ̸= 0; the conclusion is
√
−b ± b2 − 4ac
x=
.
2a
Notice that the statement says nothing about whether or not the hypothesis is true. However, if this entire statement is true and we can show that ax2 + bx + c = 0 with a ̸= 0 is
true, then the conclusion must be true. A proof of this statement might simply be a series
of equations:
ax2 + bx + c = 0
b
c
x2 + x = −
a
a
( )2 ( )2
b
b
b
c
x2 + x +
=
−
a
2a
2a
a
)2
(
2
b − 4ac
b
=
x+
2a
4a2
√
b
± b2 − 4ac
x+
=
2a
2a
√
−b ± b2 − 4ac
.
x=
2a
If we can prove a statement true, then that statement is called a proposition. A
proposition of major importance is called a theorem. Sometimes instead of proving a
theorem or proposition all at once, we break the proof down into modules; that is, we prove
several supporting propositions, which are called lemmas, and use the results of these
propositions to prove the main result. If we can prove a proposition or a theorem, we will
often, with very little effort, be able to derive other related propositions called corollaries.
Some Cautions and Suggestions
There are several different strategies for proving propositions. In addition to using different
methods of proof, students often make some common mistakes when they are first learning
CHAPTER 1. PRELIMINARIES
3
how to prove theorems. To aid students who are studying abstract mathematics for the
first time, we list here some of the difficulties that they may encounter and some of the
strategies of proof available to them. It is a good idea to keep referring back to this list as
a reminder. (Other techniques of proof will become apparent throughout this chapter and
the remainder of the text.)
• A theorem cannot be proved by example; however, the standard way to show that a
statement is not a theorem is to provide a counterexample.
• Quantifiers are important. Words and phrases such as only, for all, for every, and for
some possess different meanings.
• Never assume any hypothesis that is not explicitly stated in the theorem. You cannot
take things for granted.
• Suppose you wish to show that an object exists and is unique. First show that there
actually is such an object. To show that it is unique, assume that there are two such
objects, say r and s, and then show that r = s.
• Sometimes it is easier to prove the contrapositive of a statement. Proving the statement “If p, then q” is exactly the same as proving the statement “If not q, then not
p.”
• Although it is usually better to find a direct proof of a theorem, this task can sometimes be difficult. It may be easier to assume that the theorem that you are trying
to prove is false, and to hope that in the course of your argument you are forced to
make some statement that cannot possibly be true.
Remember that one of the main objectives of higher mathematics is proving theorems.
Theorems are tools that make new and productive applications of mathematics possible. We
use examples to give insight into existing theorems and to foster intuitions as to what new
theorems might be true. Applications, examples, and proofs are tightly interconnected—
much more so than they may seem at first appearance.
1.2 Sets and Equivalence Relations
Set Theory
A set is a well-defined collection of objects; that is, it is defined in such a manner that we
can determine for any given object x whether or not x belongs to the set. The objects that
belong to a set are called its elements or members. We will denote sets by capital letters,
such as A or X; if a is an element of the set A, we write a ∈ A.
A set is usually specified either by listing all of its elements inside a pair of braces or
by stating the property that determines whether or not an object x belongs to the set. We
might write
X = {x1 , x2 , . . . , xn }
for a set containing elements x1 , x2 , . . . , xn or
X = {x : x satisfies P}
if each x in X satisfies a certain property P. For example, if E is the set of even positive
integers, we can describe E by writing either
E = {2, 4, 6, . . .}
or E = {x : x is an even integer and x > 0}.

CHAPTER 1. PRELIMINARIES

4

We write 2 ∈ E when we want to say that 2 is in the set E, and −3 ∈

/ E to say that −3 is

not in the set E.

Some of the more important sets that we will consider are the following:

N = {n : n is a natural number} = {1, 2, 3, . . .};

Z = {n : n is an integer} = {. . . , −1, 0, 1, 2, . . .};

Q = {r : r is a rational number} = {p/q : p, q ∈ Z where q ̸= 0};

R = {x : x is a real number};

C = {z : z is a complex number}.

We can find various relations between sets as well as perform operations on sets. A set

A is a subset of B, written A ⊂ B or B ⊃ A, if every element of A is also an element of B.

For example,

{4, 5, 8} ⊂ {2, 3, 4, 5, 6, 7, 8, 9}

and

N ⊂ Z ⊂ Q ⊂ R ⊂ C.

Trivially, every set is a subset of itself. A set B is a proper subset of a set A if B ⊂ A but

B ̸= A. If A is not a subset of B, we write A ̸⊂ B; for example, {4, 7, 9} ̸⊂ {2, 4, 5, 8, 9}.

Two sets are equal, written A = B, if we can show that A ⊂ B and B ⊂ A.

It is convenient to have a set with no elements in it. This set is called the empty set

and is denoted by ∅. Note that the empty set is a subset of every set.

To construct new sets out of old sets, we can perform certain operations: the union

A ∪ B of two sets A and B is defined as

A ∪ B = {x : x ∈ A or x ∈ B};

the intersection of A and B is defined by

A ∩ B = {x : x ∈ A and x ∈ B}.

If A = {1, 3, 5} and B = {1, 2, 3, 9}, then

A ∪ B = {1, 2, 3, 5, 9} and

A ∩ B = {1, 3}.

We can consider the union and the intersection of more than two sets. In this case we write

n

∪

Ai = A1 ∪ . . . ∪ An

i=1

and

n

∩

Ai = A1 ∩ . . . ∩ An

i=1

for the union and intersection, respectively, of the sets A1 , . . . , An .

When two sets have no elements in common, they are said to be disjoint; for example,

if E is the set of even integers and O is the set of odd integers, then E and O are disjoint.

Two sets A and B are disjoint exactly when A ∩ B = ∅.

Sometimes we will work within one fixed set U , called the universal set. For any set

A ⊂ U , we define the complement of A, denoted by A′ , to be the set

A′ = {x : x ∈ U and x ∈

/ A}.

We define the difference of two sets A and B to be

A \ B = A ∩ B ′ = {x : x ∈ A and x ∈

/ B}.

CHAPTER 1. PRELIMINARIES

5

Example 1.1 Let R be the universal set and suppose that

A = {x ∈ R : 0 < x ≤ 3}
and B = {x ∈ R : 2 ≤ x < 4}.
Then
A ∩ B = {x ∈ R : 2 ≤ x ≤ 3}
A ∪ B = {x ∈ R : 0 < x < 4}
A \ B = {x ∈ R : 0 < x < 2}
A′ = {x ∈ R : x ≤ 0 or x > 3}.

□

Proposition 1.2 Let A, B, and C be sets. Then

1. A ∪ A = A, A ∩ A = A, and A \ A = ∅;

2. A ∪ ∅ = A and A ∩ ∅ = ∅;

3. A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C;

4. A ∪ B = B ∪ A and A ∩ B = B ∩ A;

5. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);

6. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Proof. We will prove (1) and (3) and leave the remaining results to be proven in the

exercises.

(1) Observe that

A ∪ A = {x : x ∈ A or x ∈ A}

= {x : x ∈ A}

=A

and

A ∩ A = {x : x ∈ A and x ∈ A}

= {x : x ∈ A}

= A.

Also, A \ A = A ∩ A′ = ∅.

(3) For sets A, B, and C,

A ∪ (B ∪ C) = A ∪ {x : x ∈ B or x ∈ C}

= {x : x ∈ A or x ∈ B, or x ∈ C}

= {x : x ∈ A or x ∈ B} ∪ C

= (A ∪ B) ∪ C.

A similar argument proves that A ∩ (B ∩ C) = (A ∩ B) ∩ C.

Theorem 1.3 De Morgan’s Laws. Let A and B be sets. Then

1. (A ∪ B)′ = A′ ∩ B ′ ;

2. (A ∩ B)′ = A′ ∪ B ′ .

■

CHAPTER 1. PRELIMINARIES

6

Proof. (1) If A ∪ B = ∅, then the theorem follows immediately since both A and B are the

empty set. Otherwise, we must show that (A ∪ B)′ ⊂ A′ ∩ B ′ and (A ∪ B)′ ⊃ A′ ∩ B ′ . Let

x ∈ (A ∪ B)′ . Then x ∈

/ A ∪ B. So x is neither in A nor in B, by the definition of the union

of sets. By the definition of the complement, x ∈ A′ and x ∈ B ′ . Therefore, x ∈ A′ ∩ B ′

and we have (A ∪ B)′ ⊂ A′ ∩ B ′ .

To show the reverse inclusion, suppose that x ∈ A′ ∩ B ′ . Then x ∈ A′ and x ∈ B ′ , and

/ B. Thus x ∈

so x ∈

/ A and x ∈

/ A ∪ B and so x ∈ (A ∪ B)′ . Hence, (A ∪ B)′ ⊃ A′ ∩ B ′ and

so (A ∪ B)′ = A′ ∩ B ′ .

The proof of (2) is left as an exercise.

■

Example 1.4 Other relations between sets often hold true. For example,

(A \ B) ∩ (B \ A) = ∅.

To see that this is true, observe that

(A \ B) ∩ (B \ A) = (A ∩ B ′ ) ∩ (B ∩ A′ )

= A ∩ A′ ∩ B ∩ B ′

= ∅.

□

Cartesian Products and Mappings

Given sets A and B, we can define a new set A × B, called the Cartesian product of A

and B, as a set of ordered pairs. That is,

A × B = {(a, b) : a ∈ A and b ∈ B}.

Example 1.5 If A = {x, y}, B = {1, 2, 3}, and C = ∅, then A × B is the set

{(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)}

and

A × C = ∅.

□

We define the Cartesian product of n sets to be

A1 × · · · × An = {(a1 , . . . , an ) : ai ∈ Ai for i = 1, . . . , n}.

If A = A1 = A2 = · · · = An , we often write An for A × · · · × A (where A would be written

n times). For example, the set R3 consists of all of 3-tuples of real numbers.

Subsets of A×B are called relations. We will define a mapping or function f ⊂ A×B

from a set A to a set B to be the special type of relation where each element a ∈ A has

a unique element b ∈ B such that (a, b) ∈ f . Another way of saying this is that for every

f

element in A, f assigns a unique element in B. We usually write f : A → B or A → B.

Instead of writing down ordered pairs (a, b) ∈ A × B, we write f (a) = b or f : a 7→ b. The

set A is called the domain of f and

f (A) = {f (a) : a ∈ A} ⊂ B

is called the range or image of f . We can think of the elements in the function’s domain

as input values and the elements in the function’s range as output values.

CHAPTER 1. PRELIMINARIES

7

Example 1.6 Suppose A = {1, 2, 3} and B = {a, b, c}. In Figure 1.7 we define relations f

and g from A to B. The relation f is a mapping, but g is not because 1 ∈ A is not assigned

to a unique element in B; that is, g(1) = a and g(1) = b.

A

B

1

f

a

2

b

3

c

g

A

B

1

a

2

b

3

c

Figure 1.7 Mappings and relations

□

Given a function f : A → B, it is often possible to write a list describing what the

function does to each specific element in the domain. However, not all functions can be

described in this manner. For example, the function f : R → R that sends each real number

to its cube is a mapping that must be described by writing f (x) = x3 or f : x 7→ x3 .

Consider the relation f : Q → Z given by f (p/q) = p. We know that 1/2 = 2/4, but

is f (1/2) = 1 or 2? This relation cannot be a mapping because it is not well-defined. A

relation is well-defined if each element in the domain is assigned to a unique element in

the range.

If f : A → B is a map and the image of f is B, i.e., f (A) = B, then f is said to be onto

or surjective. In other words, if there exists an a ∈ A for each b ∈ B such that f (a) = b,

then f is onto. A map is one-to-one or injective if a1 ̸= a2 implies f (a1 ) ̸= f (a2 ).

Equivalently, a function is one-to-one if f (a1 ) = f (a2 ) implies a1 = a2 . A map that is both

one-to-one and onto is called bijective.

Example 1.8 Let f : Z → Q be defined by f (n) = n/1. Then f is one-to-one but not onto.

Define g : Q → Z by g(p/q) = p where p/q is a rational number expressed in its lowest

terms with a positive denominator. The function g is onto but not one-to-one.

□

Given two functions, we can construct a new function by using the range of the first

function as the domain of the second function. Let f : A → B and g : B → C be mappings.

CHAPTER 1. PRELIMINARIES

8

Define a new map, the composition of f and g from A to C, by (g ◦ f )(x) = g(f (x)).

A

B

f

1

C

g

a

X

2

b

Y

3

c

Z

A

g◦f

C

1

X

2

Y

3

Z

Figure 1.9 Composition of maps

Example 1.10 Consider the functions f : A → B and g : B → C that are defined in

Figure 1.9 (top). The composition of these functions, g ◦ f : A → C, is defined in Figure 1.9

(bottom).

□

Example 1.11 Let f (x) = x2 and g(x) = 2x + 5. Then

(f ◦ g)(x) = f (g(x)) = (2x + 5)2 = 4×2 + 20x + 25

and

(g ◦ f )(x) = g(f (x)) = 2×2 + 5.

In general, order makes a difference; that is, in most cases f ◦ g ̸= g ◦ f .

Example 1.12 Sometimes it is the case that f ◦ g = g ◦ f . Let f (x) = x3 and g(x) =

Then

√

√

(f ◦ g)(x) = f (g(x)) = f ( 3 x ) = ( 3 x )3 = x

and

(g ◦ f )(x) = g(f (x)) = g(x3 ) =

√

3

√

3

□

x.

x3 = x.

□

CHAPTER 1. PRELIMINARIES

9

Example 1.13 Given a 2 × 2 matrix

(

A=

)

a b

,

c d

we can define a map TA : R2 → R2 by

TA (x, y) = (ax + by, cx + dy)

for (x, y) in R2 . This is actually matrix multiplication; that is,

(

)( ) (

)

a b

ax + by

x

=

.

c d

y

cx + dy

Maps from Rn to Rm given by matrices are called linear maps or linear transformations.

□

Example 1.14 Suppose that S = {1, 2, 3}. Define a map π : S → S by

π(1) = 2,

π(2) = 1,

π(3) = 3.

This is a bijective map. An alternative way to write π is

(

) (

)

1

2

3

1 2 3

=

.

π(1) π(2) π(3)

2 1 3

For any set S, a one-to-one and onto mapping π : S → S is called a permutation of S. □

Theorem 1.15 Let f : A → B, g : B → C, and h : C → D. Then

1. The composition of mappings is associative; that is, (h ◦ g) ◦ f = h ◦ (g ◦ f );

2. If f and g are both one-to-one, then the mapping g ◦ f is one-to-one;

3. If f and g are both onto, then the mapping g ◦ f is onto;

4. If f and g are bijective, then so is g ◦ f .

Proof. We will prove (1) and (3). Part (2) is left as an exercise. Part (4) follows directly

from (2) and (3).

(1) We must show that

h ◦ (g ◦ f ) = (h ◦ g) ◦ f .

For a ∈ A we have

(h ◦ (g ◦ f ))(a) = h((g ◦ f )(a))

= h(g(f (a)))

= (h ◦ g)(f (a))

= ((h ◦ g) ◦ f )(a).

(3) Assume that f and g are both onto functions. Given c ∈ C, we must show that

there exists an a ∈ A such that (g ◦ f )(a) = g(f (a)) = c. However, since g is onto, there

is an element b ∈ B such that g(b) = c. Similarly, there is an a ∈ A such that f (a) = b.

Accordingly,

(g ◦ f )(a) = g(f (a)) = g(b) = c.

■

CHAPTER 1. PRELIMINARIES

10

If S is any set, we will use idS or id to denote the identity mapping from S to itself.

Define this map by id(s) = s for all s ∈ S. A map g : B → A is an inverse mapping

of f : A → B if g ◦ f = idA and f ◦ g = idB ; in other words, the inverse function of a

function simply “undoes” the function. A map is said to be invertible if it has an inverse.

We usually write f −1 for the inverse of f .

√

Example 1.16 The function f (x) = x3 has inverse f −1 (x) = 3 x by Example 1.12.

□

Example 1.17 The natural logarithm and the exponential functions, f (x) = ln x and

f −1 (x) = ex , are inverses of each other provided that we are careful about choosing domains.

Observe that

f (f −1 (x)) = f (ex ) = ln ex = x

and

f −1 (f (x)) = f −1 (ln x) = eln x = x

□

whenever composition makes sense.

Example 1.18 Suppose that

(

)

3 1

A=

.

5 2

Then A defines a map from R2 to R2 by

TA (x, y) = (3x + y, 5x + 2y).

We can find an inverse map of TA by simply inverting the matrix A; that is, TA−1 = TA−1 .

In this example,

)

(

2 −1

;

A−1 =

−5 3

hence, the inverse map is given by

TA−1 (x, y) = (2x − y, −5x + 3y).

It is easy to check that

TA−1 ◦ TA (x, y) = TA ◦ TA−1 (x, y) = (x, y).

Not every map has an inverse. If we consider the map

TB (x, y) = (3x, 0)

given by the matrix

(

)

3 0

B=

,

0 0

then an inverse map would have to be of the form

TB−1 (x, y) = (ax + by, cx + dy)

and

(x, y) = TB ◦ TB−1 (x, y) = (3ax + 3by, 0)

for all x and y. Clearly this is impossible because y might not be 0.

□

CHAPTER 1. PRELIMINARIES

11

Example 1.19 Given the permutation

(

)

1 2 3

π=

2 3 1

on S = {1, 2, 3}, it is easy to see that the permutation defined by

π

−1

(

)

1 2 3

=

3 1 2

is the inverse of π. In fact, any bijective mapping possesses an inverse, as we will see in the

next theorem.

□

Theorem 1.20 A mapping is invertible if and only if it is both one-to-one and onto.

Proof. Suppose first that f : A → B is invertible with inverse g : B → A. Then

g ◦ f = idA is the identity map; that is, g(f (a)) = a. If a1 , a2 ∈ A with f (a1 ) = f (a2 ), then

a1 = g(f (a1 )) = g(f (a2 )) = a2 . Consequently, f is one-to-one. Now suppose that b ∈ B.

To show that f is onto, it is necessary to find an a ∈ A such that f (a) = b, but f (g(b)) = b

with g(b) ∈ A. Let a = g(b).

Conversely, let f be bijective and let b ∈ B. Since f is onto, there exists an a ∈ A such

that f (a) = b. Because f is one-to-one, a must be unique. Define g by letting g(b) = a. We

have now constructed the inverse of f .

■

Equivalence Relations and Partitions

A fundamental notion in mathematics is that of equality. We can generalize equality with

equivalence relations and equivalence classes. An equivalence relation on a set X is a

relation R ⊂ X × X such that

• (x, x) ∈ R for all x ∈ X (reflexive property);

• (x, y) ∈ R implies (y, x) ∈ R (symmetric property);

• (x, y) and (y, z) ∈ R imply (x, z) ∈ R (transitive property).

Given an equivalence relation R on a set X, we usually write x ∼ y instead of (x, y) ∈ R.

If the equivalence relation already has an associated notation such as =, ≡, or ∼

=, we will

use that notation.

Example 1.21 Let p, q, r, and s be integers, where q and s are nonzero. Define p/q ∼ r/s

if ps = qr. Clearly ∼ is reflexive and symmetric. To show that it is also transitive, suppose

that p/q ∼ r/s and r/s ∼ t/u, with q, s, and u all nonzero. Then ps = qr and ru = st.

Therefore,

psu = qru = qst.

Since s ̸= 0, pu = qt. Consequently, p/q ∼ t/u.

□

Example 1.22 Suppose that f and g are differentiable functions on R. We can define an

equivalence relation on such functions by letting f (x) ∼ g(x) if f ′ (x) = g ′ (x). It is clear that

∼ is both reflexive and symmetric. To demonstrate transitivity, suppose that f (x) ∼ g(x)

and g(x) ∼ h(x). From calculus we know that f (x) − g(x) = c1 and g(x) − h(x) = c2 , where

c1 and c2 are both constants. Hence,

f (x) − h(x) = (f (x) − g(x)) + (g(x) − h(x)) = c1 + c2

and f ′ (x) − h′ (x) = 0. Therefore, f (x) ∼ h(x).

□

CHAPTER 1. PRELIMINARIES

12

Example 1.23 For (x1 , y1 ) and (x2 , y2 ) in R2 , define (x1 , y1 ) ∼ (x2 , y2 ) if x21 + y12 = x22 + y22 .

Then ∼ is an equivalence relation on R2 .

□

Example 1.24 Let A and B be 2 × 2 matrices with entries in the real numbers. We can

define an equivalence relation on the set of 2 × 2 matrices, by saying A ∼ B if there exists

an invertible matrix P such that P AP −1 = B. For example, if

(

)

(

)

1 2

−18 33

A=

and B =

,

−1 1

−11 20

then A ∼ B since P AP −1 = B for

(

P =

)

2 5

.

1 3

Let I be the 2 × 2 identity matrix; that is,

(

)

1 0

I=

.

0 1

Then IAI −1 = IAI = A; therefore, the relation is reflexive. To show symmetry, suppose

that A ∼ B. Then there exists an invertible matrix P such that P AP −1 = B. So

A = P −1 BP = P −1 B(P −1 )−1 .

Finally, suppose that A ∼ B and B ∼ C. Then there exist invertible matrices P and Q

such that P AP −1 = B and QBQ−1 = C. Since

C = QBQ−1 = QP AP −1 Q−1 = (QP )A(QP )−1 ,

the relation is transitive. Two matrices that are equivalent in this manner are said to be

similar.

□

A partition ∪

P of a set X is a collection of nonempty sets X1 , X2 , . . . such that Xi ∩Xj =

∅ for i ̸= j and k Xk = X. Let ∼ be an equivalence relation on a set X and let x ∈ X.

Then [x] = {y ∈ X : y ∼ x} is called the equivalence class of x. We will see that

an equivalence relation gives rise to a partition via equivalence classes. Also, whenever

a partition of a set exists, there is some natural underlying equivalence relation, as the

following theorem demonstrates.

Theorem 1.25 Given an equivalence relation ∼ on a set X, the equivalence classes of X

form a partition of X. Conversely, if P = {Xi } is a partition of a set X, then there is an

equivalence relation on X with equivalence classes Xi .

Proof. Suppose there exists an equivalence relation ∼ on the set X. For any

∪ x ∈ X, the

reflexive property shows that x ∈ [x] and so [x] is nonempty. Clearly X = x∈X [x]. Now

let x, y ∈ X. We need to show that either [x] = [y] or [x] ∩ [y] = ∅. Suppose that the

intersection of [x] and [y] is not empty and that z ∈ [x] ∩ [y]. Then z ∼ x and z ∼ y. By

symmetry and transitivity x ∼ y; hence, [x] ⊂ [y]. Similarly, [y] ⊂ [x] and so [x] = [y].

Therefore, any two equivalence classes are either disjoint or exactly the same.

Conversely, suppose that P = {Xi } is a partition of a set X. Let two elements be

equivalent if they are in the same partition. Clearly, the relation is reflexive. If x is in the

same partition as y, then y is in the same partition as x, so x ∼ y implies y ∼ x. Finally,

if x is in the same partition as y and y is in the same partition as z, then x must be in the

same partition as z, and transitivity holds.

■

CHAPTER 1. PRELIMINARIES

13

Corollary 1.26 Two equivalence classes of an equivalence relation are either disjoint or

equal.

Let us examine some of the partitions given by the equivalence classes in the last set of

examples.

Example 1.27 In the equivalence relation in Example 1.21, two pairs of integers, (p, q) and

(r, s), are in the same equivalence class when they reduce to the same fraction in its lowest

□

terms.

Example 1.28 In the equivalence relation in Example 1.22, two functions f (x) and g(x)

are in the same partition when they differ by a constant.

□

Example 1.29 We defined an equivalence class on R2 by (x1 , y1 ) ∼ (x2 , y2 ) if x21 + y12 =

x22 + y22 . Two pairs of real numbers are in the same partition when they lie on the same

circle about the origin.

□

Example 1.30 Let r and s be two integers and suppose that n ∈ N. We say that r is

congruent to s modulo n, or r is congruent to s mod n, if r − s is evenly divisible by n;

that is, r − s = nk for some k ∈ Z. In this case we write r ≡ s (mod n). For example,

41 ≡ 17 (mod 8) since 41 − 17 = 24 is divisible by 8. We claim that congruence modulo

n forms an equivalence relation of Z. Certainly any integer r is equivalent to itself since

r − r = 0 is divisible by n. We will now show that the relation is symmetric. If r ≡ s

(mod n), then r − s = −(s − r) is divisible by n. So s − r is divisible by n and s ≡ r

(mod n). Now suppose that r ≡ s (mod n) and s ≡ t (mod n). Then there exist integers

k and l such that r − s = kn and s − t = ln. To show transitivity, it is necessary to prove

that r − t is divisible by n. However,

r − t = r − s + s − t = kn + ln = (k + l)n,

and so r − t is divisible by n.

If we consider the equivalence relation established by the integers modulo 3, then

[0] = {. . . , −3, 0, 3, 6, . . .},

[1] = {. . . , −2, 1, 4, 7, . . .},

[2] = {. . . , −1, 2, 5, 8, . . .}.

Notice that [0] ∪ [1] ∪ [2] = Z and also that the sets are disjoint. The sets [0], [1], and [2]

form a partition of the integers.

The integers modulo n are a very important example in the study of abstract algebra

and will become quite useful in our investigation of various algebraic structures such as

groups and rings. In our discussion of the integers modulo n we have actually assumed a

result known as the division algorithm, which will be stated and proved in Chapter 2. □

1.3 Reading Questions

1.

What do relations and mappings have in common?

2.

What makes relations and mappings different?

3.

State carefully the three defining properties of an equivalence relation. In other words,

do not just name the properties, give their definitions.

4.

What is the big deal about equivalence relations? (Hint: Partitions.)

5.

Describe a general technique for proving that two sets are equal.

CHAPTER 1. PRELIMINARIES

14

1.4 Exercises

1.

Suppose that

A = {x : x ∈ N and x is even},

B = {x : x ∈ N and x is prime},

C = {x : x ∈ N and x is a multiple of 5}.

Describe each of the following sets.

(a) A ∩ B

2.

(c) A ∪ B

(b) B ∩ C

(d) A ∩ (B ∪ C)

If A = {a, b, c}, B = {1, 2, 3}, C = {x}, and D = ∅, list all of the elements in each of

the following sets.

(a) A × B

(c) A × B × C

3.

(b) B × A

(d) A × D

Find an example of two nonempty sets A and B for which A × B = B × A is true.

4.

5.

6.

Prove A ∪ ∅ = A and A ∩ ∅ = ∅.

Prove A ∪ B = B ∪ A and A ∩ B = B ∩ A.

Prove A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

7.

Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

8.

Prove A ⊂ B if and only if A ∩ B = A.

9.

Prove (A ∩ B)′ = A′ ∪ B ′ .

10. Prove A ∪ B = (A ∩ B) ∪ (A \ B) ∪ (B \ A).

11. Prove (A ∪ B) × C = (A × C) ∪ (B × C).

12. Prove (A ∩ B) \ B = ∅.

13. Prove (A ∪ B) \ B = A \ B.

14. Prove A \ (B ∪ C) = (A \ B) ∩ (A \ C).

15. Prove A ∩ (B \ C) = (A ∩ B) \ (A ∩ C).

16. Prove (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B).

17. Which of the following relations f : Q → Q define a mapping? In each case, supply a

reason why f is or is not a mapping.

p+q

p+1

(c) f (p/q) =

(a) f (p/q) =

q2

p−2

3p

3p2 p

(d) f (p/q) = 2 −

3q

7q

q

18. Determine which of the following functions are one-to-one and which are onto. If the

function is not onto, determine its range.

(b) f (p/q) =

(a) f : R → R defined by f (x) = ex

(b) f : Z → Z defined by f (n) = n2 + 3

(c) f : R → R defined by f (x) = sin x

(d) f : Z → Z defined by f (x) = x2

CHAPTER 1. PRELIMINARIES

15

19. Let f : A → B and g : B → C be invertible mappings; that is, mappings such that

f −1 and g −1 exist. Show that (g ◦ f )−1 = f −1 ◦ g −1 .

20.

(a) Define a function f : N → N that is one-to-one but not onto.

(b) Define a function f : N → N that is onto but not one-to-one.

21. Prove the relation defined on R2 by (x1 , y1 ) ∼ (x2 , y2 ) if x21 + y12 = x22 + y22 is an

equivalence relation.

22. Let f : A → B and g : B → C be maps.

(a) If f and g are both one-to-one functions, show that g ◦ f is one-to-one.

(b) If g ◦ f is onto, show that g is onto.

(c) If g ◦ f is one-to-one, show that f is one-to-one.

(d) If g ◦ f is one-to-one and f is onto, show that g is one-to-one.

(e) If g ◦ f is onto and g is one-to-one, show that f is onto.

23. Define a function on the real numbers by

f (x) =

x+1

.

x−1

What are the domain and range of f ? What is the inverse of f ? Compute f ◦ f −1 and

f −1 ◦ f .

24. Let f : X → Y be a map with A1 , A2 ⊂ X and B1 , B2 ⊂ Y .

(a) Prove f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 ).

(b) Prove f (A1 ∩ A2 ) ⊂ f (A1 ) ∩ f (A2 ). Give an example in which equality fails.

(c) Prove f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ), where

f −1 (B) = {x ∈ X : f (x) ∈ B}.

(d) Prove f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 ).

(e) Prove f −1 (Y \ B1 ) = X \ f −1 (B1 ).

25. Determine whether or not the following relations are equivalence relations on the given

set. If the relation is an equivalence relation, describe the partition given by it. If the

relation is not an equivalence relation, state why it fails to be one.

(a) x ∼ y in R if x ≥ y

(c) x ∼ y in R if |x − y| ≤ 4

(b) m ∼ n in Z if mn > 0

(d) m ∼ n in Z if m ≡ n (mod 6)

2

26. Define a relation ∼ on R by stating that (a, b) ∼ (c, d) if and only if a2 + b2 ≤ c2 + d2 .

Show that ∼ is reflexive and transitive but not symmetric.

27. Show that an m × n matrix gives rise to a well-defined map from Rn to Rm .

28. Find the error in the following argument by providing a counterexample. “The reflexive

property is redundant in the axioms for an equivalence relation. If x ∼ y, then y ∼ x

by the symmetric property. Using the transitive property, we can deduce that x ∼ x.”

29. Projective Real Line. Define a relation on R2 \ {(0, 0)} by letting (x1 , y1 ) ∼ (x2 , y2 )

if there exists a nonzero real number λ such that (x1 , y1 ) = (λx2 , λy2 ). Prove that ∼

CHAPTER 1. PRELIMINARIES

16

defines an equivalence relation on R2 \ (0, 0). What are the corresponding equivalence

classes? This equivalence relation defines the projective line, denoted by P(R), which

is very important in geometry.

1.5 References and Suggested Readings

[1]

Artin, M. Algebra (Classic Version). 2nd ed. Pearson, Upper Saddle River, NJ, 2018.

[2]

Childs, L. A Concrete Introduction to Higher Algebra. 2nd ed. Springer-Verlag, New

York, 1995.

[3]

Dummit, D. and Foote, R. Abstract Algebra. 3rd ed. Wiley, New York, 2003.

[4]

Ehrlich, G. Fundamental Concepts of Algebra. PWS-KENT, Boston, 1991.

[5]

Fraleigh, J. B. A First Course in Abstract Algebra. 7th ed. Pearson, Upper Saddle

River, NJ, 2003.

[6]

Gallian, J. A. Contemporary Abstract Algebra. 7th ed. Brooks/Cole, Belmont, CA,

2009.

[7]

Halmos, P. Naive Set Theory. Springer, New York, 1991. One of the best references

for set theory.

[8]

Herstein, I. N. Abstract Algebra. 3rd ed. Wiley, New York, 1996.

[9]

Hungerford, T. W. Algebra. Springer, New York, 1974. One of the standard graduate

algebra texts.

[10] Lang, S. Algebra. 3rd ed. Springer, New York, 2002. Another standard graduate text.

[11] Lidl, R. and Pilz, G. Applied Abstract Algebra. 2nd ed. Springer, New York, 1998.

[12] Mackiw, G. Applications of Abstract Algebra. Wiley, New York, 1985.

[13] Nickelson, W. K. Introduction to Abstract Algebra. 3rd ed. Wiley, New York, 2006.

[14] Solow, D. How to Read and Do Proofs. 5th ed. Wiley, New York, 2009.

[15] van der Waerden, B. L. A History of Algebra. Springer-Verlag, New York, 1985. An

account of the historical development of algebra.

1.6 Sage

Sage is a powerful system for studying and exploring many different areas of mathematics.

In this textbook, you will study a variety of algebraic structures, such as groups, rings and

fields. Sage does an excellent job of implementing many features of these objects as we will

see in the chapters ahead. But here and now, in this initial chapter, we will concentrate on

a few general ways of getting the most out of working with Sage.

You may use Sage several different ways. It may be used as a command-line program

when installed on your own computer. Or it might be a web application such as the

SageMathCloud. Our writing will assume that you are reading this as a worksheet within

the Sage Notebook (a web browser interface), or this is a section of the entire book presented

as web pages, and you are employing the Sage Cell Server via those pages. After the first

few chapters the explanations should work equally well for whatever vehicle you use to

execute Sage commands.

CHAPTER 1. PRELIMINARIES

17

Executing Sage Commands

Most of your interaction will be by typing commands into a compute cell. If you are reading

this in the Sage Notebook or as a webpage version of the book, then you will see a compute

cell just below this paragraph. Click once inside the compute cell and if you are in the Sage

Notebook, you will get a more distinctive border around it, a blinking cursor inside, plus a

cute little “evaluate” link below.At the cursor, type 2+2 and then click on the evaluate link.

Did a 4 appear below the cell? If so, you have successfully sent a command off for Sage to

evaluate and you have received back the (correct) answer.

Here is another compute cell. Try evaluating the command factorial(300) here.Hmmmmm.

That is quite a big integer! If you see slashes at the end of each line, this means the result

is continued onto the next line, since there are 615 total digits in the result.

To make new compute cells in the Sage Notebook (only), hover your mouse just above

another compute cell, or just below some output from a compute cell. When you see a

skinny blue bar across the width of your worksheet, click and you will open up a new

compute cell, ready for input. Note that your worksheet will remember any calculations

you make, in the order you make them, no matter where you put the cells, so it is best to

stay organized and add new cells at the bottom.

Try placing your cursor just below the monstrous value of 300! that you have. Click on

the blue bar and try another factorial computation in the new compute cell.

Each compute cell will show output due to only the very last command in the cell. Try

to predict the following output before evaluating the cell.

a

b

b

a

a

=

=

=

=

10

6

b – 10

a + 20

30

The following compute cell will not print anything since the one command does not

create output. But it will have an effect, as you can see when you execute the subsequent

cell. Notice how this uses the value of b from above. Execute this compute cell once.

Exactly once. Even if it appears to do nothing. If you execute the cell twice, your credit

card may be charged twice.

b = b + 50

Now execute this cell, which will produce some output.

b + 20

66

So b came into existence as 6. We subtracted 10 immediately afterward. Then a

subsequent cell added 50. This assumes you executed this cell exactly once! In the last

cell we create b+20 (but do not save it) and it is this value (66) that is output, while b is

still 46.

You can combine several commands on one line with a semi-colon. This is a great way

to get multiple outputs from a compute cell. The syntax for building a matrix should be

somewhat obvious when you see the output, but if not, it is not particularly important to

understand now.

CHAPTER 1. PRELIMINARIES

18

A = matrix ([[3 , 1] , [5 ,2]]) ; A

[3 1]

[5 2]

print ( A) ; print () ; print (A . inverse () )

[3 1]

[5 2]

< BLANKLINE >

[ 2 -1]

[ -5 3]

Immediate Help

Some commands in Sage are “functions,” an example is factorial() above. Other commands are “methods” of an object and are like characteristics of objects, an example is

.inverse() as a method of a matrix. Once you know how to create an object (such as a

matrix), then it is easy to see all the available methods. Write the name of the object, place

a period (“dot”) and hit the TAB key. If you have A defined from above, then the compute

cell below is ready to go, click into it and then hit TAB (not “evaluate”!). You should get

a long list of possible methods.

A.

To get some help on how to use a method with an object, write its name after a dot (with

no parentheses) and then use a question-mark and hit TAB. (Hit the escape key “ESC” to

remove the list, or click on the text for a method.)

A . inverse ?

With one more question-mark and a TAB you can see the actual computer instructions

that were programmed into Sage to make the method work, once you scoll down past the

documentation delimited by the triple quotes (“””):

A . inverse ??

It is worthwhile to see what Sage does when there is an error. You will probably see a

lot of these at first, and initially they will be a bit intimidating. But with time, you will

learn how to use them effectively and you will also become more proficient with Sage and

see them less often. Execute the compute cell below, it asks for the inverse of a matrix that

has no inverse. Then reread the commentary.

B = matrix ([[2 , 20] , [5 , 50]])

B . inverse ()

Traceback ( most recent call last ) :

…

ZeroDivisionError : matrix must be nonsingular

Click just to the left of the error message to expand it fully (another click hides it totally,

and a third click brings back the abbreviated form). Read the bottom of an error message

first, it is your best explanation. Here a ZeroDivisionError is not 100% accurate, but is

CHAPTER 1. PRELIMINARIES

19

close. The matrix is not invertible, not dissimilar to how we cannot divide scalars by zero.

The remainder of the message begins at the top showing were the error first happened in

your code and then the various places where intermediate functions were called, until the

actual piece of Sage where the problem occurred. Sometimes this information will give you

some clues, sometimes it is totally undecipherable. So do not let it scare you if it seems

mysterious, but do remember to always read the last line first, then go back and read the

first few lines for something that looks like your code.

Annotating Your Work

It is easy to comment on your work when you use the Sage Notebook. (The following only

applies if you are reading this within a Sage Notebook. If you are not, then perhaps you

can go open up a worksheet in the Sage Notebook and experiment there.) You can open up

a small word-processor by hovering your mouse until you get a skinny blue bar again, but

now when you click, also hold the SHIFT key at the same time. Experiment with fonts,

colors, bullet lists, etc and then click the “Save changes” button to exit. Double-click on

your text if you need to go back and edit it later.

Open the word-processor again to create a new bit of text (maybe next to the empty

compute cell just below). Type all of the following exactly,

Pythagorean Theorem: $c^2=a^2+b^2$

and save your changes. The symbols between the dollar signs are written according to the

mathematical typesetting language known as TEX — cruise the internet to learn more about

this very popular tool. (Well, it is extremely popular among mathematicians and physical

scientists.)

Lists

Much of our interaction with sets will be through Sage lists. These are not really sets — they

allow duplicates, and order matters. But they are so close to sets, and so easy and powerful

to use that we will use them regularly. We will use a fun made-up list for practice, the

quote marks mean the items are just text, with no special mathematical meaning. Execute

these compute cells as we work through them.

zoo = [ ‘ snake ‘ , ‘ parrot ‘ , ‘ elephant ‘ , ‘ baboon ‘ , ‘ beetle ‘ ]

zoo

[ ‘ snake ‘ , ‘ parrot ‘ , ‘ elephant ‘ , ‘ baboon ‘ , ‘ beetle ‘ ]

So the square brackets define the boundaries of our list, commas separate items, and we

can give the list a name. To work with just one element of the list, we use the name and

a pair of brackets with an index. Notice that lists have indices that begin counting at zero.

This will seem odd at first and will seem very natural later.

zoo [2]

‘ elephant ‘

We can add a new creature to the zoo, it is joined up at the far right end.

zoo . append ( ‘ ostrich ‘ ) ; zoo

[ ‘ snake ‘ , ‘ parrot ‘ , ‘ elephant ‘ , ‘ baboon ‘ , ‘ beetle ‘ , ‘ ostrich ‘ ]

We can remove a creature.

CHAPTER 1. PRELIMINARIES

20

zoo . remove ( ‘ parrot ‘ )

zoo

[ ‘ snake ‘ , ‘ elephant ‘ , ‘ baboon ‘ , ‘ beetle ‘ , ‘ ostrich ‘ ]

We can extract a sublist. Here we start with element 1 (the elephant) and go all the

way up to, but not including, element 3 (the beetle). Again a bit odd, but it will feel natural

later. For now, notice that we are extracting two elements of the lists, exactly 3 − 1 = 2

elements.

mammals = zoo [1:3]

mammals

[ ‘ elephant ‘ , ‘ baboon ‘ ]

Often we will want to see if two lists are equal. To do that we will need to sort a list

first. A function creates a new, sorted list, leaving the original alone. So we need to save

the new one with a new name.

newzoo = sorted ( zoo )

newzoo

[ ‘ baboon ‘ , ‘ beetle ‘ , ‘ elephant ‘ , ‘ ostrich ‘ , ‘ snake ‘ ]

zoo . sort ()

zoo

[ ‘ baboon ‘ , ‘ beetle ‘ , ‘ elephant ‘ , ‘ ostrich ‘ , ‘ snake ‘ ]

Notice that if you run this last compute cell your zoo has changed and some commands

above will not necessarily execute the same way. If you want to experiment, go all the way

back to the first creation of the zoo and start executing cells again from there with a fresh

zoo.

A construction called a list comprehension is especially powerful, especially since it

almost exactly mirrors notation we use to describe sets. Suppose we want to form the plural

of the names of the creatures in our zoo. We build a new list, based on all of the elements

of our old list.

plurality_zoo = [ animal + ‘ s ‘ for animal in zoo ]

plurality_zoo

[ ‘ baboons ‘ , ‘ beetles ‘ , ‘ elephants ‘ , ‘ ostrichs ‘ , ‘ snakes ‘ ]

Almost like it says: we add an “s” to each animal name, for each animal in the zoo, and

place them in a new list. Perfect. (Except for getting the plural of “ostrich” wrong.)

Lists of Integers

One final type of list, with numbers this time. The srange() function will create lists of

integers. (The “s” in the name stands for “Sage” and so will produce integers that Sage

understands best. Many early difficulties with Sage and group theory can be alleviated by

using only this command to create lists of integers.) In its simplest form an invocation

like srange(12) will create a list of 12 integers, starting at zero and working up to, but not

including, 12. Does this sound familiar?

CHAPTER 1. PRELIMINARIES

21

dozen = srange (12) ; dozen

[0 , 1, 2 , 3 , 4, 5 , 6 , 7 , 8 , 9 , 10 , 11]

Here are two other forms, that you should be able to understand by studying the examples.

teens = srange (13 , 20) ; teens

[13 , 14 , 15 , 16 , 17 , 18 , 19]

decades = srange (1900 , 2000 , 10) ; decades

[1900 , 1910 , 1920 , 1930 , 1940 , 1950 , 1960 , 1970 , 1980 , 1990]

Saving and Sharing Your Work

There is a “Save” button in the upper-right corner of the Sage Notebook. This will save a

current copy of your worksheet that you can retrieve your work from within your notebook

again later, though you have to re-execute all the cells when you re-open the worksheet.

There is also a “File” drop-down list, on the left, just above your very top compute cell

(not be confused with your browser’s File menu item!). You will see a choice here labeled

“Save worksheet to a file…” When you do this, you are creating a copy of your worksheet

in the sws format (short for “Sage WorkSheet”). You can email this file, or post it on a

website, for other Sage users and they can use the “Upload” link on the homepage of their

notebook to incorporate a copy of your worksheet into their notebook.

There are other ways to share worksheets that you can experiment with, but this gives

you one way to share any worksheet with anybody almost anywhere.

We have covered a lot here in this section, so come back later to pick up tidbits you

might have missed. There are also many more features in the Sage Notebook that we have

not covered.

1.7 Sage Exercises

1.

This exercise is just about making sure you know how to use Sage. You may be

using the Sage Notebook server the online CoCalc service through your web browser.

In either event, create a new worksheet. Do some non-trivial computation, maybe a

pretty plot or some gruesome numerical computation to an insane precision. Create

an interesting list and experiment with it some. Maybe include some nicely formatted

text or TEX using the included mini-word-processor of the Sage Notebook (hover until

a blue bar appears between cells and then shift-click) or create commentary in cells

within CoCalc using the magics %html or %md on a line of their own followed by text

in html or Markdown syntax (respectively).

Use whatever mechanism your instructor has in place for submitting your work.

Or save your worksheet and then trade with a classmate.

2

The Integers

The integers are the building blocks of mathematics. In this chapter we will investigate

the fundamental properties of the integers, including mathematical induction, the division

algorithm, and the Fundamental Theorem of Arithmetic.

2.1 Mathematical Induction

Suppose we wish to show that

1 + 2 + ··· + n =

n(n + 1)

2

for any natural number n. This formula is easily verified for small numbers such as n = 1,

2, 3, or 4, but it is impossible to verify for all natural numbers on a case-by-case basis. To

prove the formula true in general, a more generic method is required.

Suppose we have verified the equation for the first n cases. We will attempt to show

that we can generate the formula for the (n + 1)th case from this knowledge. The formula

is true for n = 1 since

1(1 + 1)

1=

.

2

If we have verified the first n cases, then

n(n + 1)

+n+1

2

n2 + 3n + 2

=

2

(n + 1)[(n + 1) + 1]

=

.

2

1 + 2 + · · · + n + (n + 1) =

This is exactly the formula for the (n + 1)th case.

This method of proof is known as mathematical induction. Instead of attempting to

verify a statement about some subset S of the positive integers N on a case-by-case basis, an

impossible task if S is an infinite set, we give a specific proof for the smallest integer being

considered, followed by a generic argument showing that if the statement holds for a given

case, then it must also hold for the next case in the sequence. We summarize mathematical

induction in the following axiom.

Principle 2.1 First Principle of Mathematical Induction. Let S(n) be a statement

about integers for n ∈ N and suppose S(n0 ) is true for some integer n0 . If for all integers k

22

CHAPTER 2. THE INTEGERS

23

with k ≥ n0 , S(k) implies that S(k + 1) is true, then S(n) is true for all integers n greater

than or equal to n0 .

Example 2.2 For all integers n ≥ 3, 2n > n + 4. Since

8 = 23 > 3 + 4 = 7,

the statement is true for n0 = 3. Assume that 2k > k + 4 for k ≥ 3. Then 2k+1 = 2 · 2k >

2(k + 4). But

2(k + 4) = 2k + 8 > k + 5 = (k + 1) + 4

since k is positive. Hence, by induction, the statement holds for all integers n ≥ 3.

□

Example 2.3 Every integer 10n+1 + 3 · 10n + 5 is divisible by 9 for n ∈ N. For n = 1,

101+1 + 3 · 10 + 5 = 135 = 9 · 15

is divisible by 9. Suppose that 10k+1 + 3 · 10k + 5 is divisible by 9 for k ≥ 1. Then

10(k+1)+1 + 3 · 10k+1 + 5 = 10k+2 + 3 · 10k+1 + 50 − 45

= 10(10k+1 + 3 · 10k + 5) − 45

□

is divisible by 9.

Example 2.4 We will prove the binomial theorem using mathematical induction; that is,

n

(a + b) =

n ( )

∑

n

k=0

k

ak bn−k ,

where a and b are real numbers, n ∈ N, and

( )

n

n!

=

k!(n − k)!

k

is the binomial coefficient. We first show that

(

) ( ) (

)

n+1

n

n

=

+

.

k

k

k−1

This result follows from

( ) (

)

n

n

n!

n!

+

=

+

k

k−1

k!(n − k)! (k − 1)!(n − k + 1)!

(n + 1)!

=

k!(n + 1 − k)!

(

)

n+1

=

.

k

If n = 1, the binomial theorem is easy to verify. Now assume that the result is true for n

greater than or equal to 1. Then

(a + b)n+1 = (a + b)(a + b)n

( n ( )

)

∑ n

k n−k

= (a + b)

a b

k

k=0

CHAPTER 2. THE INTEGERS

=

n ( )

∑

n

k=0

k

ak+1 bn−k +

24

n ( )

∑

n

k=0

k

ak bn+1−k

)

n (

n ( )

∑

∑

n

n k n+1−k

n+1

k n+1−k

=a

+

a b

+

a b

+ bn+1

k−1

k

k=1

k=1

) ( )]

n [(

∑

n

n

= an+1 +

+

ak bn+1−k + bn+1

k−1

k

k=1

(

n+1

∑ n + 1)

=

ak bn+1−k .

k

k=0

□

We have an equivalent statement of the Principle of Mathematical Induction that is

often very useful.

Principle 2.5 Second Principle of Mathematical Induction. Let S(n) be a statement

about integers for n ∈ N and suppose S(n0 ) is true for some integer n0 . If S(n0 ), S(n0 +

1), . . . , S(k) imply that S(k + 1) for k ≥ n0 , then the statement S(n) is true for all integers

n ≥ n0 .

A nonempty subset S of Z is well-ordered if S contains a least element. Notice that

the set Z is not well-ordered since it does not contain a smallest element. However, the

natural numbers are well-ordered.

Principle 2.6 Principle of Well-Ordering. Every nonempty subset of the natural

numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

Lemma 2.7 The Principle of Mathematical Induction implies that 1 is the least positive

natural number.

Proof. Let S = {n ∈ N : n ≥ 1}. Then 1 ∈ S. Assume that n ∈ S. Since 0 < 1, it must
be the case that n = n + 0 < n + 1. Therefore, 1 ≤ n < n + 1. Consequently, if n ∈ S, then
n + 1 must also be in S, and by the Principle of Mathematical Induction, and S = N. ■
Theorem 2.8 The Principle of Mathematical Induction implies the Principle of WellOrdering. That is, every nonempty subset of N contains a least element.
Proof. We must show that if S is a nonempty subset of the natural numbers, then S
contains a least element. If S contains 1, then the theorem is true by Lemma 2.7. Assume
that if S contains an integer k such that 1 ≤ k ≤ n, then S contains a least element. We
will show that if a set S contains an integer less than or equal to n + 1, then S has a least
element. If S does not contain an integer less than n + 1, then n + 1 is the smallest integer
in S. Otherwise, since S is nonempty, S must contain an integer less than or equal to n. In
this case, by induction, S contains a least element.
■
Induction can also be very useful in formulating definitions. For instance, there are two
ways to define n!, the factorial of a positive integer n.
• The explicit definition: n! = 1 · 2 · 3 · · · (n − 1) · n.
• The inductive or recursive definition: 1! = 1 and n! = n(n − 1)! for n > 1.

Every good mathematician or computer scientist knows that looking at problems recursively,

as opposed to explicitly, often results in better understanding of complex issues.

CHAPTER 2. THE INTEGERS

25

2.2 The Division Algorithm

An application of the Principle of Well-Ordering that we will use often is the division

algorithm.

Theorem 2.9 Division Algorithm. Let a and b be integers, with b > 0. Then there

exist unique integers q and r such that

a = bq + r

where 0 ≤ r < b.
Proof. This is a perfect example of the existence-and-uniqueness type of proof. We must
first prove that the numbers q and r actually exist. Then we must show that if q ′ and r′
are two other such numbers, then q = q ′ and r = r′ .
Existence of q and r. Let
S = {a − bk : k ∈ Z and a − bk ≥ 0}.
If 0 ∈ S, then b divides a, and we can let q = a/b and r = 0. If 0 ∈
/ S, we can use the WellOrdering Principle. We must first show that S is nonempty. If a > 0, then a − b · 0 ∈ S. If

a < 0, then a − b(2a) = a(1 − 2b) ∈ S. In either case S ̸= ∅. By the Well-Ordering Principle,
S must have a smallest member, say r = a − bq. Therefore, a = bq + r, r ≥ 0. We now show
that r < b. Suppose that r > b. Then

a − b(q + 1) = a − bq − b = r − b > 0.

In this case we would have a − b(q + 1) in the set S. But then a − b(q + 1) < a − bq, which
would contradict the fact that r = a − bq is the smallest member of S. So r ≤ b. Since
0∈
/ S, r ̸= b and so r < b.
Uniqueness of q and r. Suppose there exist integers r, r′ , q, and q ′ such that
a = bq + r, 0 ≤ r < b
and
a = bq ′ + r′ , 0 ≤ r′ < b.
Then bq +r = bq ′ +r′ . Assume that r′ ≥ r. From the last equation we have b(q −q ′ ) = r′ −r;
therefore, b must divide r′ − r and 0 ≤ r′ − r ≤ r′ < b. This is possible only if r′ − r = 0.
Hence, r = r′ and q = q ′ .
■
Let a and b be integers. If b = ak for some integer k, we write a | b. An integer d is
called a common divisor of a and b if d | a and d | b. The greatest common divisor of
integers a and b is a positive integer d such that d is a common divisor of a and b and if d′
is any other common divisor of a and b, then d′ | d. We write d = gcd(a, b); for example,
gcd(24, 36) = 12 and gcd(120, 102) = 6. We say that two integers a and b are relatively
prime if gcd(a, b) = 1.
Theorem 2.10 Let a and b be nonzero integers. Then there exist integers r and s such that
gcd(a, b) = ar + bs.
Furthermore, the greatest common divisor of a and b is unique.
Proof. Let
S = {am + bn : m, n ∈ Z and am + bn > 0}.

Clearly, the set S is nonempty; hence, by the Well-Ordering Principle S must have a smallest

member, say d = ar + bs. We claim that d = gcd(a, b). Write a = dq + r′ where 0 ≤ r′ < d.
CHAPTER 2. THE INTEGERS
26
If r′ > 0, then

r′ = a − dq

= a − (ar + bs)q

= a − arq − bsq

= a(1 − rq) + b(−sq),

which is in S. But this would contradict the fact that d is the smallest member of S. Hence,

r′ = 0 and d divides a. A similar argument shows that d divides b. Therefore, d is a common

divisor of a and b.

Suppose that d′ is another common divisor of a and b, and we want to show that d′ | d.

If we let a = d′ h and b = d′ k, then

d = ar + bs = d′ hr + d′ ks = d′ (hr + ks).

So d′ must divide d. Hence, d must be the unique greatest common divisor of a and b.

■

Corollary 2.11 Let a and b be two integers that are relatively prime. Then there exist

integers r and s such that ar + bs = 1.

The Euclidean Algorithm

Among other things, Theorem 2.10 allows us to compute the greatest common divisor of

two integers.

Example 2.12 Let us compute the greatest common divisor of 945 and 2415. First observe

that

2415 = 945 · 2 + 525

945 = 525 · 1 + 420

525 = 420 · 1 + 105

420 = 105 · 4 + 0.

Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415.

Hence, 105 divides both 945 and 2415. If d were another common divisor of 945 and 2415,

then d would also have to divide 105. Therefore, gcd(945, 2415) = 105.

If we work backward through the above sequence of equations, we can also obtain numbers r and s such that 945r + 2415s = 105. Observe that

105 = 525 + (−1) · 420

= 525 + (−1) · [945 + (−1) · 525]

= 2 · 525 + (−1) · 945

= 2 · [2415 + (−2) · 945] + (−1) · 945

= 2 · 2415 + (−5) · 945.

So r = −5 and s = 2. Notice that r and s are not unique, since r = 41 and s = −16 would

also work.

□

To compute gcd(a, b) = d, we are using repeated divisions to obtain a decreasing sequence of positive integers r1 > r2 > · · · > rn = d; that is,

b = aq1 + r1

CHAPTER 2. THE INTEGERS

27

a = r1 q2 + r2

r1 = r2 q3 + r3

..

.

rn−2 = rn−1 qn + rn

rn−1 = rn qn+1 .

To find r and s such that ar + bs = d, we begin with this last equation and substitute

results obtained from the previous equations:

d = rn

= rn−2 − rn−1 qn

= rn−2 − qn (rn−3 − qn−1 rn−2 )

= −qn rn−3 + (1 + qn qn−1 )rn−2

..

.

= ra + sb.

The algorithm that we have just used to find the greatest common divisor d of two integers

a and b and to write d as the linear combination of a and b is known as the Euclidean

algorithm.

Prime Numbers

Let p be an integer such that p > 1. We say that p is a prime number, or simply p is

prime, if the only positive numbers that divide p are 1 and p itself. An integer n > 1 that

is not prime is said to be composite.

Lemma 2.13 Euclid. Let a and b be integers and p be a prime number. If p | ab, then

either p | a or p | b.

Proof. Suppose that p does not divide a. We must show that p | b. Since gcd(a, p) = 1,

there exist integers r and s such that ar + ps = 1. So

b = b(ar + ps) = (ab)r + p(bs).

Since p divides both ab and itself, p must divide b = (ab)r + p(bs).

■

Theorem 2.14 Euclid. There exist an infinite number of primes.

Proof. We will prove this theorem by contradiction. Suppose that there are only a finite

number of primes, say p1 , p2 , . . . , pn . Let P = p1 p2 · · · pn + 1. Then P must be divisible

by some pi for 1 ≤ i ≤ n. In this case, pi must divide P − p1 p2 · · · pn = 1, which is a

contradiction. Hence, either P is prime or there exists an additional prime number p ̸= pi

that divides P .

■

Theorem 2.15 Fundamental Theorem of Arithmetic. Let n be an integer such that

n > 1. Then

n = p1 p2 · · · pk ,

where p1 , . . . , pk are primes (not necessarily distinct). Furthermore, this factorization is

unique; that is, if

n = q1 q2 · · · ql ,

then k = l and the qi ’s are just the pi ’s rearranged.

CHAPTER 2. THE INTEGERS

28

Proof. Uniqueness. To show uniqueness we will use induction on n. The theorem is

certainly true for n = 2 since in this case n is prime. Now assume that the result holds for

all integers m such that 1 ≤ m < n, and
n = p1 p2 · · · pk = q1 q2 · · · ql ,
where p1 ≤ p2 ≤ · · · ≤ pk and q1 ≤ q2 ≤ · · · ≤ ql . By Lemma 2.13, p1 | qi for some
i = 1, . . . , l and q1 | pj for some j = 1, . . . , k. Since all of the pi ’s and qi ’s are prime, p1 = qi
and q1 = pj . Hence, p1 = q1 since p1 ≤ pj = q1 ≤ qi = p1 . By the induction hypothesis,
n′ = p2 · · · pk = q2 · · · ql
has a unique factorization. Hence, k = l and qi = pi for i = 1, . . . , k.
Existence. To show existence, suppose that there is some integer that cannot be written
as the product of primes. Let S be the set of all such numbers. By the Principle of WellOrdering, S has a smallest number, say a. If the only positive factors of a are a and 1, then
a is prime, which is a contradiction. Hence, a = a1 a2 where 1 < a1 < a and 1 < a2 < a.
Neither a1 ∈ S nor a2 ∈ S, since a is the smallest element in S. So
a1 = p1 · · · pr
a2 = q1 · · · qs .
Therefore,
a = a1 a2 = p1 · · · pr q1 · · · qs .
So a ∈
/ S, which is a contradiction.
■
Historical Note
Prime numbers were first studied by the ancient Greeks. Two important results from antiquity are Euclid’s proof that an infinite number of primes exist and the Sieve of Eratosthenes,
a method of computing all of the prime numbers less than a fixed positive integer n. One
problem in number theory is to find a function f such that f (n) is prime for each integer n.
n
Pierre Fermat (1601?–1665) conjectured that 22 + 1 was prime for all n, but later it was
shown by Leonhard Euler (1707–1783) that
5
22 + 1 = 4,294,967,297
is a composite number. One of the many unproven conjectures about prime numbers is
Goldbach’s Conjecture. In a letter to Euler in 1742, Christian Goldbach stated the conjecture that every even integer with the exception of 2 seemed to be the sum of two primes:
4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, . . .. Although the conjecture has been verified for the
numbers up through 4 × 1018 , it has yet to be proven in general. Since prime numbers play
an important role in public key cryptography, there is currently a great deal of interest in
determining whether or not a large number is prime.
2.3 Reading Questions
1.
Use Sage to express 123456792 as a product of prime numbers.
2.
Find the greatest common divisor of 84 and 52.
3.
Find integers r and s so that r(84) + s(52) = gcd(84, 52).
4.
Explain the use of the term “induction hypothesis.”
CHAPTER 2. THE INTEGERS
5.
29
What is Goldbach’s Conjecture? And why is it called a “conjecture”?
2.4 Exercises
1.
Prove that
12 + 22 + · · · + n2 =
2.
n(n + 1)(2n + 1)
6
for n ∈ N.
Prove that
13 + 23 + · · · + n3 =
3.
4.
n2 (n + 1)2
4
for n ∈ N.
Prove that n! > 2n for n ≥ 4.

Prove that

x + 4x + 7x + · · · + (3n − 2)x =

n(3n − 1)x

2

5.

for n ∈ N.

Prove that 10n+1 + 10n + 1 is divisible by 3 for n ∈ N.

6.

Prove that 4 · 102n + 9 · 102n−1 + 5 is divisible by 99 for n ∈ N.

7.

Show that

√

n

1∑

ak .

n

n

a1 a2 · · · an ≤

k=1

8.

Prove the Leibniz rule for

that

f (n) (x),

(f g)

(n)

where

f (n)

is the nth derivative of f ; that is, show

n ( )

∑

n (k)

(x) =

f (x)g (n−k) (x).

k

k=0

9. Use induction to prove that 1 + 2 + 22 + · · · + 2n = 2n+1 − 1 for n ∈ N.

10. Prove that

1 1

1

n

+ + ··· +

=

2 6

n(n + 1)

n+1

for n ∈ N.

11. If x is a nonnegative real number, then show that (1 + x)n − 1 ≥ nx for n = 0, 1, 2, . . ..

12. Power Sets. Let X be a set. Define the power set of X, denoted P(X), to be the

set of all subsets of X. For example,

P({a, b}) = {∅, {a}, {b}, {a, b}}.

For every positive integer n, show that a set with exactly n elements has a power set

with exactly 2n elements.

13. Prove that the two principles of mathematical induction stated in Section 2.1 are

equivalent.

14. Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the

smallest natural number. Use this result to show that the Principle of Well-Ordering

implies the Principle of Mathematical Induction; that is, show that if S ⊂ N such that

1 ∈ S and n + 1 ∈ S whenever n ∈ S, then S = N.

CHAPTER 2. THE INTEGERS

30

15. For each of the following pairs of numbers a and b, calculate gcd(a, b) and find integers

r and s such that gcd(a, b) = ra + sb.

(a) 14 and 39

(d) 471 and 562

(b) 234 and 165

(e) 23771 and 19945

(c) 1739 and 9923

(f) −4357 and 3754

16. Let a and b be nonzero integers. If there exist integers r and s such that ar + bs = 1,

show that a and b are relatively prime.

17. Fibonacci Numbers. The Fibonacci numbers are

1, 1, 2, 3, 5, 8, 13, 21, . . . .

We can define them inductively by f1 = 1, f2 = 1, and fn+2 = fn+1 + fn for n ∈ N.

(a) Prove that fn < 2n .
(b) Prove that fn+1 fn−1 = fn2 + (−1)n , n ≥ 2.
√
√
√
(c) Prove that fn = [(1 + 5 )n − (1 − 5 )n ]/2n 5.
√
(d) Show that limn→∞ fn /fn+1 = ( 5 − 1)/2.
(e) Prove that fn and fn+1 are relatively prime.
18. Let a and b be integers such that gcd(a, b) = 1. Let r and s be integers such that
ar + bs = 1. Prove that
gcd(a, s) = gcd(r, b) = gcd(r, s) = 1.
19. Let x, y ∈ N be relatively prime. If xy is a perfect square, prove that x and y must
both be perfect squares.
20. Using the division algorithm, show that every perfect square is of the form 4k or 4k + 1
for some nonnegative integer k.
21. Suppose that a, b, r, s are pairwise relatively prime and that
a2 + b2 = r2
a2 − b2 = s2 .
Prove that a, r, and s are odd and b is even.
22. Let n ∈ N. Use the division algorithm to prove that every integer is congruent mod n
to precisely one of the integers 0, 1, . . . , n − 1. Conclude that if r is an integer, then
there is exactly one s in Z such that 0 ≤ s < n and [r] = [s]. Hence, the integers are
indeed partitioned by congruence mod n.
23. Define the least common multiple of two nonzero integers a and b, denoted by
lcm(a, b), to be the nonnegative integer m such that both a and b divide m, and if a
and b divide any other integer n, then m also divides n. Prove there exists a unique
least common multiple for any two integers a and b.
24. If d = gcd(a, b) and m = lcm(a, b), prove that dm = |ab|.
25. Show that lcm(a, b) = ab if and only if gcd(a, b) = 1.
26. Prove that gcd(a, c) = gcd(b, c) = 1 if and only if gcd(ab, c) = 1 for integers a, b, and
c.
27. Let a, b, c ∈ Z. Prove that if gcd(a, b) = 1 and a | bc, then a | c.
CHAPTER 2. THE INTEGERS
28.
29.
30.
31.
31
Let p ≥ 2. Prove that if 2p − 1 is prime, then p must also be prime.
Prove that there are an infinite number of primes of the form 6n + 5.
Prove that there are an infinite number of primes of the form 4n − 1.
Using the fact that 2 is prime, show that
√ there do not exist integers p and q such that
2
2
p = 2q . Demonstrate that therefore 2 cannot be a rational number.
2.5 Programming Exercises
1.
The Sieve of Eratosthenes. One method of computing all of the prime numbers
less than a certain fixed positive integer N is to list all of the numbers n such that
1 < n < N . Begin by eliminating all of the multiples of 2. Next eliminate all of the
multiples of 3. Now eliminate all of the multiples of 5. Notice that 4 has already been
crossed out. Continue in this
√ manner, noticing that we do not have to go all the way
to N ; it suffices to stop at N . Using this method, compute all of the prime numbers
less than N = 250. We can also use this method to find all of the integers that are
relatively prime to an integer N . Simply eliminate the prime factors of N and all of
their multiples. Using this method, find all of the numbers that are relatively prime
to N = 120. Using the Sieve of Eratosthenes, write a program that will compute all
of the primes less than an integer N .
2.
Let N0 = N ∪ {0}. Ackermann’s function is the function A : N0 × N0 → N0 defined by
the equations
A(0, y) = y + 1,
A(x + 1, 0) = A(x, 1),
A(x + 1, y + 1) = A(x, A(x + 1, y)).
Use this definition to compute A(3, 1). Write a program to evaluate Ackermann’s
function. Modify the program to count the number of statements executed in the
program when Ackermann’s function is evaluated. How many statements are executed
in the evaluation of A(4, 1)? What about A(5, 1)?
3.
Write a computer program that will implement the Euclidean algorithm. The program
should accept two positive integers a and b as input and should output gcd(a, b) as
well as integers r and s such that
gcd(a, b) = ra + sb.
2.6 References and Suggested Readings
[1]
Brookshear, J. G. Theory of Computation: Formal Languages, Automata, and Complexity. Benjamin/Cummings, Redwood City, CA, 1989. Shows the relationships of
the theoretical aspects of computer science to set theory and the integers.
[2]
Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers. 6th ed.
Oxford University Press, New York, 2008.
[3]
Niven, I. and Zuckerman, H. S. An Introduction to the Theory of Numbers. 5th ed.
Wiley, New York, 1991.
CHAPTER 2. THE INTEGERS
[4]
32
Vanden Eynden, C. Elementary Number Theory. 2nd ed. Waveland Press, Long
Grove IL, 2001.
2.7 Sage
Many properties of the algebraic objects we will study can be determined from properties
of associated integers. And Sage has many powerful functions for analyzing integers.
Division Algorithm
The code a % b will return the remainder upon division of a by b. In other words, the
result is the unique integer r such that (1) 0 ≤ r < b, and (2) a = bq + r for some integer
q (the quotient), as guaranteed by the Division Algorithm (Theorem 2.9). Then (a − r)/b
will equal q. For example,
r = 14 % 3
r
2
q = (14 - r ) /3
q
4
It is also possible to get both the quotient and remainder at the same time with the
.quo_rem() method (quotient and remainder).
a = 14
b = 3
a . quo_rem ( b)
(4 , 2)
A remainder of zero indicates divisibility. So (a % b) == 0 will return True if b divides
a, and will otherwise return False.
(20 % 5) == 0
True
(17 % 4) == 0
False
The .divides() method is another option.
c = 5
c . divides (20)
True
CHAPTER 2. THE INTEGERS
33
d = 4
d . divides (17)
False
Greatest Common Divisor
The greatest common divisor of a and b is obtained with the command gcd(a, b), where
in our first uses, a and b are integers. Later, a and b can be other objects with a notion of
divisibility and “greatness,” such as polynomials. For example,
gcd (2776 , 2452)
4
We can use the gcd command to determine if a pair of integers are relatively prime.
a = 31049
b = 2105
gcd (a , b) == 1
True
a = 3563
b = 2947
gcd (a , b) == 1
False
The command xgcd(a,b)(“eXtended GCD”) returns a triple where the first element is
the greatest common divisor of a and b (as with the gcd(a,b) command above), but the
next two elements are values of r and s such that ra + sb = gcd(a, b).
xgcd (633 ,331)
(1 , -137 , 262)
Portions of the triple can be extracted using [ ](“indexing”) to access the entries of the
triple, starting with the first as number 0. For example, the following should always return
the result True, even if you change the values of a and b. Try changing the values of a and
b below, to see that the result is always True.
a = 633
b = 331
extended = xgcd (a , b )
g = extended [0]
r = extended [1]
s = extended [2]
g == r *a + s * b
True
Studying this block of code will go a long way towards helping you get the most out of
Sage’s output. Note that = is how a value is assigned to a variable, while as in the last line,
== is how we compare two items for equality.
CHAPTER 2. THE INTEGERS
34
Primes and Factoring
The method .is_prime() will determine if an integer is prime or not.
a = 117371
a . is_prime ()
True
b = 14547073
b . is_prime ()
False
b == 1597 * 9109
True
The command random_prime(a, proof=True) will generate a random prime number
between 2 and a. Experiment by executing the following two compute cells several times.
(Replacing proof=True by proof=False will speed up the search, but there will be a very,
very, very small probability the result will not be prime.)
a = random_prime (10^21 , proof = True )
a
424729101793542195193
a . is_prime ()
True
The command prime_range(a, b) returns an ordered list of all the primes from a to
b − 1, inclusive. For example,
prime_range (500 , 550)
[503 , 509 , 521 , 523 , 541 , 547]
The commands next_prime(a) and previous_prime(a) are other ways to get a single
prime number of a desired size. Give them a try below if you have an empty compute cell
there (as you will if you are reading in the Sage Notebook, or are reading the online version).
(The hash symbol, #, is used to indicate a “comment” line, which will not be evaluated by
Sage. So erase this line, or start on the one below it.)In addition to checking if integers are
prime or not, or generating prime numbers, Sage can also decompose any integer into its
prime factors, as described by the Fundamental Theorem of Arithmetic (Theorem 2.15).
a = 2600
a . factor ()
2^3 * 5^2 * 13
So 2600 = 23 × 52 × 13 and this is the unique way to write 2600 as a product of prime
numbers (other than rearranging the order of the primes themselves in the product).
CHAPTER 2. THE INTEGERS
35
While Sage will print a factorization nicely, it is carried internally as a list of pairs of
integers, with each pair being a base (a prime number) and an exponent (a positive integer).
Study the following carefully, as it is another good exercise in working with Sage output in
the form of lists.
a = 2600
factored = a . factor ()
first_term = factored [0]
first_term
(2 , 3)
second_term = factored [1]
second_term
(5 , 2)
third_term = factored [2]
third_term
(13 , 1)
first_prime = first_term [0]
first_prime
2
first_exponent = first_term [1]
first_exponent
3
The next compute cell reveals the internal version of the factorization by asking for the
actual list. And we show how you could determine exactly how many terms the factorization
has by using the length command, len().
list ( factored )
[(2 , 3) , (5 , 2) , (13 , 1) ]
len ( factored )
3
Can you extract the next two primes, and their exponents, from a?
2.8 Sage Exercises
These exercises are about investigating basic properties of the integers, something we will
frequently do when investigating groups. Sage worksheets have extensive capabilities for
making new cells with carefully formatted text, include support for LATEX syntax to express
CHAPTER 2. THE INTEGERS
36
mathematics. So when a question asks for explanation or commentary, make a new cell and
communicate clearly with your audience.
1.
2.
3.
4.
5.
6.
Use the next_prime() command to construct two different 8-digit prime numbers and
save them in variables named a and b.
Use the .is_prime() method to verify that your primes a and b are really prime.
Verify that 1 is the greatest common divisor of your two primes from the previous
exercises.
Find two integers that make a “linear combination” of your two primes equal to 1.
Include a verification of your result.
Determine a factorization into powers of primes for c = 4 598 037 234.
Write a compute cell that defines the same value of c again, and then defines a candidate
divisor of c named d. The third line of the cell should return True if and only if d is
a divisor of c. Illustrate the use of your cell by testing your code with d = 7 and in a
new copy of the cell, testing your code with d = 11.
3
Groups
We begin our study of algebraic structures by investigating s...

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more