Concrete Abstract Algebra: From Numbers to

Concrete Abstract Algebra develops the theory of abstract algebra from numbers to Gröbner bases, whilst taking in all the usual material of a traditional introductory course. In addition there is a rich supply of topics like cryptography, factoring algorithms for integers, quadratic residues, finite fields, factoring algorithms for polynomials and systems of non-linear equations. A special feature is that Gröbner bases do not appear as an isolated example. They are fully integrated as a subject that can be successfully taught in an undergraduate context. Lauritzen's approach to teaching abstract algebra is based on an extensive use of examples, applications and exercises. The basic philosophy is that inspiring, non-trivial applications and examples give motivation and ease the learning of abstract concepts. This book is built on several years of experience teaching introductory abstract algebra at Aarhus, where the emphasis on concrete and inspiring examples has improved student performance significantly. Solutions to the exercises are available to lecturers from solutions@cambridge.org.

Preface

xi

Acknowledgements

xiv

1 Numbers

1

(49)

1.1 The natural numbers and the integers

3

(1)

1.1.1 Well ordering and mathematical induction

3

(1)

1.2 Division with remainder

4

(1)

1.3 Congruences

5

(3)

1.3.1 Repeated squaring - an example

7

(1)

1.4 Greatest common divisor

8

(1)

1.5 The Euclidean algorithm

9

(5)

1.6 The Chinese remainder theorem

14

(3)

1.7 Euler's theorem

17

(2)

1.8 Prime numbers

19

(5)

1.8.1 There are infinitely many prime numbers

20

(2)

1.8.2 Unique factorization

22

(2)

1.8.3 How to compute φ(n)

24

(1)

1.9 RSA explained

24

(6)

1.9.1 Encryption and decryption exponents

25

(1)

1.9.2 Finding astronomical prime numbers

26

(4)

1.10 Algorithms for prime factorization

30

(6)

1.10.1 The birthday problem

30

(1)

1.10.2 Pollard's ρ-algorithm

31

(2)

1.10.3 Pollard's (p -1)-algorithm

33

(1)

1.10.4 The Fermat-Kraitchik algorithm

34

(2)

1.11 Quadratic residues

36

(5)

1.12 Exercises

41

(9)

2 Groups

50

(61)

2.1 Definition

50

(10)

2.1.1 Groups and congruences

51

(2)

2.1.2 The composition table

53

(1)

2.1.3 Associativity

54

(1)

2.1.4 The first non-abelian group

54

(1)

2.1.5 Uniqueness of neutral and inverse elements

55

(1)

2.1.6 Multiplication by g € G is bijective

56

(1)

2.1.7 More examples of groups

57

(3)

2.2 Subgroups and cosecs

60

(4)

2.2.1 Subgroups of Z

61

(1)

2.2.2 Cosecs

61

(3)

2.3 Normal subgroups

64

(4)

2.3.1 Quotient groups of the integers

66

(1)

2.3.2 The multiplicative group of prime residue classes

66

(2)

2.4 Group homomorphisms

68

(3)

2.5 The isomorphism theorem

71

(1)

2.6 Order of a group element

72

(2)

2.7 Cyclic groups

74

(2)

2.8 Groups and numbers

76

(2)

2.8.1 Euler's theorem

76

(1)

2.8.2 Product groups

76

(1)

2.8.3 The Chinese remainder theorem

77

(1)

2.9 Symmetric and alternating groups

78

(14)

2.9.1 Cycles

79

(3)

2.9.2 Simple transpositions and "bubble" sort

82

(3)

2.9.3 The alternating group

85

(1)

2.9.4 Simple groups

86

(2)

2.9.5 The 15-puzzle

88

(4)

2.10 Actions of groups

92

(12)

2.10.1 Conjugacy classes

98

(1)

2.10.2 Conjugacy classes in the symmetric group

98

(2)

2.10.3 Groups of order pr

100

(1)

2.10.4 The Sylow theorems

101

(3)

2.11 Exercises

104

(7)

3 Rings

111

(32)

3.1 Definition

112

(4)

3.1.1 Ideals

115

(1)

3.2 Quotient rings

116

(3)

3.2.1 Quotient rings of Z

117

(1)

3.2.2 Prime ideals

118

(1)

3.2.3 Maximal ideals

118

(1)

3.3 Ring homomorphisms

119

(4)

3.3.1 The unique ring homomorphism from Z

120

(1)

3.3.2 Freshman's Dream

121

(2)

3.4 Fields of fractions

123

(2)

3.5 Unique factorization

125

(13)

3.5.1 Divisibility and greatest common divisor

126

(1)

3.5.2 Irreducible elements

126

(1)

3.5.3 Prime elements

127

(3)

3.5.4 Euclidean domains

130

(2)

3.5.5 Fermat's two-square theorem

132

(2)

3.5.6 The Euclidean algorithm strikes again

134

(1)

3.5.7 Prime numbers congruent to 1 modulo 4

135

(2)

3.5.8 Fermat's last theorem

137

(1)

3.6 Exercises

138

(5)

4 Polynomials

143

(43)

4.1 Polynomial rings

144

(3)

4.1.1 Binomial coefficients modulo a prime number

146

(1)

4.2 Division of polynomials

147

(3)

4.3 Roots of polynomials

150

(4)

4.3.1 Differentiation of polynomials

153

(1)

4.4 Cyclotomic polynomials

154

(3)

4.5 Primitive roots

157

(4)

4.5.1 Decimal expansions and primitive roots

159

(1)

4.5.2 Primitive roots and public key cryptography

160

(1)

4.5.3 Yet another application of cyclotomic polynomials

160

(1)

4.6 Ideals in polynomial rings

161

(6)

4.6.1 Polynomial rings modulo ideals

164

(3)

4.7 Theorema Aureum: the law of quadratic reciprocity

167

(3)

4.8 Finite fields

170

(6)

4.8.1 Existence of finite fields

172

(1)

4.8.2 Uniqueness of finite fields

172

(1)

4.8.3 A beautiful identity

173

(3)

4.9 Berlekamp's algorithm

176

(3)

4.10 Exercises

179

(7)

5 Gröbner bases

186

(37)

5.1 Polynomials in several variables

187

(6)

5.1.1 Term orderings

189

(4)

5.2 The initial term of a polynomial

193

(1)

5.3 The division algorithm

194

(2)

5.4 Gröbner bases

196

(4)

5.4.1 Hilbert's basis theorem

198

(2)

5.5 Newton revisited

200

(3)

5.6 Buchberger's S-criterion

203

(5)

5.6.1 The S-polynomials

204

(4)

5.6.2 The S-criterion

208

(1)

5.7 Buchberger's algorithm

208

(4)

5.8 The reduced Gröbner basis

212

(2)

5.9 Solving equations using Gröbner bases

214

(3)

5.10 Exercises

217

(6)

Appendix A Relations

223

(7)

A.1 Basic definitions and properties

223

(1)

A.2 Equivalence relations

224

(4)

A.2.1 Construction of the integers Z

226

(1)

A.2.2 Construction of the rational numbers Q

227

(1)

A.3 Partial orderings

228

(2)

Appendix B Linear algebra

230

(4)

B.1 Linear independence

231

(1)

B.2 Dimension

232

(2)

References

234

(2)

Index

236

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Concrete Abstract Algebra: From Numbers to GrÃ¶bner Bases

Summary

Table of Contents

Supplemental Materials