MATH 3GR3 McMaster University Abstract Algebra Questions

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