Note to Students |
|
xvii | |
Preface |
|
xix | |
|
|
1 | (42) |
|
1 The Integers: An Introduction |
|
|
3 | (8) |
|
|
4 | (1) |
|
|
5 | (2) |
|
|
7 | (1) |
|
|
8 | (1) |
|
|
8 | (1) |
|
|
9 | (2) |
|
2 Divisibility of Integers |
|
|
11 | (12) |
|
|
12 | (1) |
|
|
13 | (1) |
|
The Well-Ordering Principle |
|
|
14 | (1) |
|
Proving the Division Algorithm |
|
|
15 | (2) |
|
|
17 | (1) |
|
|
18 | (2) |
|
|
20 | (1) |
|
|
20 | (3) |
|
3 Greatest Common Divisors |
|
|
23 | (10) |
|
|
24 | (1) |
|
Calculating Greatest Common Divisors |
|
|
25 | (1) |
|
|
26 | (1) |
|
GCDs and Linear Combinations |
|
|
27 | (3) |
|
Well-Ordering, GCDs, and Linear Combinations |
|
|
30 | (1) |
|
|
31 | (1) |
|
|
31 | (2) |
|
|
33 | (10) |
|
|
33 | (1) |
|
|
34 | (1) |
|
The Fundamental Theorem of Arithmetic |
|
|
34 | (1) |
|
|
35 | (1) |
|
|
36 | (2) |
|
|
38 | (1) |
|
Primes and Irreducibles in Other Number Systems |
|
|
38 | (2) |
|
|
40 | (1) |
|
|
40 | (3) |
|
|
43 | (34) |
|
5 Equivalence Relations and Zn |
|
|
45 | (18) |
|
|
46 | (1) |
|
|
47 | (2) |
|
|
49 | (1) |
|
|
50 | (2) |
|
|
52 | (3) |
|
Zero Divisors and Units in Zn |
|
|
55 | (2) |
|
|
57 | (1) |
|
|
58 | (5) |
|
6 Algebra in Other Number Systems |
|
|
63 | (14) |
|
|
64 | (2) |
|
Subsets of the Real Numbers |
|
|
66 | (2) |
|
|
68 | (1) |
|
|
69 | (1) |
|
|
70 | (1) |
|
|
71 | (3) |
|
|
74 | (1) |
|
|
75 | (2) |
|
|
77 | (58) |
|
7 An Introduction to Rings |
|
|
79 | (12) |
|
|
79 | (2) |
|
Basic Properties of Rings |
|
|
81 | (1) |
|
Commutative Rings and Rings with Identity |
|
|
81 | (1) |
|
Uniqueness of Identities and Inverses |
|
|
82 | (2) |
|
Zero Divisors and Multiplicative Cancellation |
|
|
84 | (2) |
|
Fields and Integral Domains |
|
|
86 | (1) |
|
|
86 | (1) |
|
|
87 | (2) |
|
|
89 | (2) |
|
8 Integer Multiples and Exponents |
|
|
91 | (14) |
|
|
92 | (1) |
|
Integer Multiplication and Exponentiation |
|
|
93 | (1) |
|
Nonpositive Multiples and Exponents |
|
|
94 | (1) |
|
Properties of Integer Multiplication and Exponentiation |
|
|
95 | (4) |
|
The Characteristic of a Ring |
|
|
99 | (2) |
|
|
101 | (1) |
|
|
102 | (2) |
|
|
104 | (1) |
|
9 Subrings, Extensions, and Direct Sums |
|
|
105 | (16) |
|
|
106 | (1) |
|
|
107 | (3) |
|
Subfields and Field Extensions |
|
|
110 | (3) |
|
|
113 | (3) |
|
|
116 | (1) |
|
|
116 | (3) |
|
|
119 | (2) |
|
10 Isomorphism and Invariants |
|
|
121 | (14) |
|
|
122 | (2) |
|
|
124 | (3) |
|
|
125 | (1) |
|
|
125 | (2) |
|
|
127 | (3) |
|
|
129 | (1) |
|
|
130 | (1) |
|
|
130 | (1) |
|
|
131 | (2) |
|
|
133 | (1) |
|
|
134 | (1) |
|
|
135 | (80) |
|
|
137 | (16) |
|
|
138 | (4) |
|
Polynomials over an Integral Domain |
|
|
142 | (1) |
|
|
143 | (2) |
|
|
145 | (1) |
|
|
146 | (2) |
|
|
148 | (1) |
|
Appendix -- Proof that R[ x] Is a Commutative Ring |
|
|
148 | (5) |
|
12 Divisibility in Polynomial Rings |
|
|
153 | (14) |
|
|
153 | (2) |
|
The Division Algorithm in F[ x] |
|
|
155 | (4) |
|
Greatest Common Divisors of Polynomials |
|
|
159 | (2) |
|
Relatively Prime Polynomials |
|
|
161 | (1) |
|
The Euclidean Algorithm for Polynomials |
|
|
162 | (2) |
|
|
164 | (1) |
|
|
164 | (1) |
|
|
165 | (2) |
|
13 Roots, Factors, and Irreducible Polynomials |
|
|
167 | (12) |
|
Polynomial Functions and Remainders |
|
|
168 | (1) |
|
Roots of Polynomials and the Factor Theorem |
|
|
169 | (2) |
|
|
171 | (2) |
|
Unique Factorization in F[ x] |
|
|
173 | (3) |
|
|
176 | (1) |
|
|
177 | (1) |
|
|
178 | (1) |
|
14 Irreducible Polynomials |
|
|
179 | (20) |
|
|
180 | (1) |
|
|
180 | (1) |
|
|
181 | (1) |
|
|
182 | (3) |
|
Polynomials with No Linear Factors in Q[ x] |
|
|
185 | (2) |
|
Reducing Polynomials in Z[ x] Modulo Primes |
|
|
187 | (1) |
|
|
188 | (1) |
|
Factorization in F[ x] for Other Fields F |
|
|
189 | (1) |
|
|
189 | (1) |
|
|
190 | (3) |
|
|
193 | (1) |
|
|
194 | (2) |
|
Appendix -- Proof of the Fundamental Theorem of Algebra |
|
|
196 | (3) |
|
15 Quotients of Polynomial Rings |
|
|
199 | (16) |
|
|
200 | (1) |
|
Congruence Modulo a Polynomial |
|
|
200 | (1) |
|
Congruence Classes of Polynomials |
|
|
200 | (1) |
|
|
201 | (2) |
|
Special Quotients of Polynomial Rings |
|
|
203 | (2) |
|
|
205 | (3) |
|
|
208 | (1) |
|
|
209 | (3) |
|
|
212 | (3) |
|
|
215 | (54) |
|
16 Ideals and Homomorphisms |
|
|
217 | (22) |
|
|
218 | (1) |
|
|
218 | (5) |
|
Congruence Modulo an Ideal |
|
|
223 | (2) |
|
|
225 | (2) |
|
|
227 | (3) |
|
The Kernel and Image of a Homomorphism |
|
|
230 | (1) |
|
The First Isomorphism Theorem for Rings |
|
|
231 | (2) |
|
|
233 | (1) |
|
|
233 | (4) |
|
|
237 | (2) |
|
17 Divisibility and Factorization in Integral Domains |
|
|
239 | (10) |
|
|
239 | (1) |
|
Divisibility and Euclidean Domains |
|
|
240 | (1) |
|
|
240 | (2) |
|
Unique Factorization Domains |
|
|
242 | (1) |
|
Proof 1 Generalizing Greatest Common Divisors |
|
|
243 | (1) |
|
Proof 2 Principal Ideal Domains |
|
|
244 | (3) |
|
|
247 | (1) |
|
|
247 | (1) |
|
|
248 | (1) |
|
|
249 | (20) |
|
|
250 | (1) |
|
|
250 | (2) |
|
|
252 | (2) |
|
|
254 | (2) |
|
|
256 | (1) |
|
|
257 | (3) |
|
|
260 | (1) |
|
A Characterization of the Integers |
|
|
261 | (3) |
|
|
264 | (1) |
|
|
264 | (3) |
|
|
267 | (2) |
|
|
269 | (202) |
|
|
271 | (12) |
|
|
271 | (1) |
|
|
272 | (1) |
|
Symmetries of Regular Polygons |
|
|
273 | (4) |
|
|
277 | (1) |
|
|
278 | (5) |
|
20 An Introduction to Groups |
|
|
283 | (12) |
|
|
284 | (1) |
|
|
285 | (1) |
|
Basic Properties of Groups |
|
|
286 | (1) |
|
Identities and Inverses in a Group |
|
|
287 | (1) |
|
|
288 | (1) |
|
|
288 | (2) |
|
|
290 | (1) |
|
|
291 | (2) |
|
|
293 | (2) |
|
21 Integer Powers of Elements in a Group |
|
|
295 | (8) |
|
|
295 | (1) |
|
Powers of Elements in a Group |
|
|
296 | (4) |
|
|
300 | (1) |
|
|
300 | (2) |
|
|
302 | (1) |
|
|
303 | (14) |
|
|
304 | (1) |
|
|
304 | (2) |
|
|
306 | (1) |
|
The Subgroup Generated by an Element |
|
|
307 | (2) |
|
|
309 | (1) |
|
|
310 | (4) |
|
|
314 | (3) |
|
23 Subgroups of Cyclic Groups |
|
|
317 | (8) |
|
|
318 | (1) |
|
Subgroups of Cyclic Groups |
|
|
318 | (1) |
|
Properties of the Order of an Element |
|
|
319 | (2) |
|
|
321 | (1) |
|
|
322 | (1) |
|
|
322 | (1) |
|
|
322 | (3) |
|
|
325 | (8) |
|
|
326 | (1) |
|
Relationships between Elements in Dn |
|
|
326 | (2) |
|
Generators and Group Presentations |
|
|
328 | (1) |
|
|
329 | (1) |
|
|
330 | (2) |
|
|
332 | (1) |
|
|
333 | (14) |
|
|
334 | (1) |
|
The Symmetric Group of a Set |
|
|
334 | (1) |
|
Permutation Notation and Cycles |
|
|
335 | (1) |
|
The Cycle Decomposition of a Permutation |
|
|
336 | (3) |
|
|
339 | (2) |
|
Even and Odd Permutations and the Alternating Group |
|
|
341 | (1) |
|
|
342 | (1) |
|
|
342 | (4) |
|
|
346 | (1) |
|
26 Cosets and Lagrange's Theorem |
|
|
347 | (12) |
|
|
347 | (1) |
|
|
348 | (1) |
|
|
349 | (1) |
|
|
350 | (3) |
|
|
353 | (1) |
|
|
354 | (3) |
|
|
357 | (2) |
|
27 Normal Subgroups and Quotient Groups |
|
|
359 | (22) |
|
|
360 | (1) |
|
|
361 | (1) |
|
|
362 | (2) |
|
|
364 | (1) |
|
Cauchy's Theorem for Finite Abelian Groups |
|
|
365 | (2) |
|
Simple Groups and the Simplicity of An |
|
|
367 | (5) |
|
|
372 | (1) |
|
|
373 | (6) |
|
|
379 | (2) |
|
|
381 | (12) |
|
External Direct Products of Groups |
|
|
382 | (2) |
|
Orders of Elements in Direct Products |
|
|
384 | (1) |
|
Internal Direct Products in Groups |
|
|
385 | (3) |
|
|
388 | (1) |
|
|
389 | (2) |
|
|
391 | (2) |
|
29 Group Isomorphisms and Invariants |
|
|
393 | (26) |
|
|
395 | (2) |
|
|
397 | (3) |
|
|
397 | (1) |
|
|
398 | (2) |
|
|
400 | (1) |
|
Some Basic Properties of Isomorphisms |
|
|
401 | (1) |
|
|
401 | (1) |
|
|
402 | (1) |
|
|
403 | (1) |
|
|
403 | (4) |
|
Isomorphisms and Cyclic Groups |
|
|
407 | (2) |
|
|
409 | (2) |
|
|
411 | (1) |
|
|
412 | (4) |
|
|
416 | (3) |
|
30 Homomorphisms and Isomorphism Theorems |
|
|
419 | (14) |
|
|
420 | (1) |
|
The Kernel of a Homomorphism |
|
|
421 | (1) |
|
The Image of a Homomorphism |
|
|
422 | (1) |
|
The Isomorphism Theorems for Groups |
|
|
423 | (4) |
|
The First Isomorphism Theorem for Groups |
|
|
423 | (1) |
|
The Second Isomorphism Theorem for Groups |
|
|
424 | (1) |
|
The Third Isomorphism Theorem for Groups |
|
|
425 | (1) |
|
The Fourth Isomorphism Theorem for Groups |
|
|
425 | (2) |
|
|
427 | (1) |
|
|
427 | (4) |
|
|
431 | (2) |
|
31 The Fundamental Theorem of Finite Abelian Groups |
|
|
433 | (14) |
|
|
434 | (1) |
|
|
434 | (5) |
|
|
439 | (4) |
|
|
443 | (1) |
|
|
444 | (3) |
|
32 The First Sylow Theorem |
|
|
447 | (14) |
|
|
448 | (1) |
|
Conjugacy and the Class Equation |
|
|
448 | (4) |
|
|
450 | (2) |
|
|
452 | (1) |
|
|
452 | (2) |
|
The Second and Third Sylow Theorems |
|
|
454 | (2) |
|
|
456 | (1) |
|
|
457 | (2) |
|
|
459 | (2) |
|
33 The Second and Third Sylow Theorems |
|
|
461 | (10) |
|
|
462 | (1) |
|
Conjugate Subgroups and Normalizers |
|
|
462 | (2) |
|
|
464 | (2) |
|
|
466 | (1) |
|
|
467 | (1) |
|
|
468 | (3) |
|
|
471 | (64) |
|
|
473 | (10) |
|
|
474 | (1) |
|
Congruence and Modular Arithmetic |
|
|
474 | (1) |
|
The Basics of RSA Encryption |
|
|
475 | (1) |
|
|
476 | (2) |
|
|
478 | (2) |
|
Concluding Thoughts and Notes |
|
|
480 | (1) |
|
|
480 | (3) |
|
|
483 | (10) |
|
|
483 | (1) |
|
|
484 | (1) |
|
|
484 | (1) |
|
|
485 | (1) |
|
Verhoeff's Dihedral Group D5 Check |
|
|
486 | (2) |
|
|
488 | (1) |
|
|
489 | (2) |
|
|
491 | (2) |
|
36 Games: NIM and the 15 Puzzle |
|
|
493 | (12) |
|
|
493 | (5) |
|
|
498 | (5) |
|
Permutations and the 15 Puzzle |
|
|
499 | (1) |
|
|
500 | (3) |
|
|
503 | (1) |
|
|
503 | (1) |
|
|
504 | (1) |
|
37 Finite Fields, the Group of Units in Zn, and Splitting Fields |
|
|
505 | (16) |
|
|
505 | (1) |
|
|
506 | (2) |
|
The Group of Units of a Finite Field |
|
|
508 | (2) |
|
|
510 | (2) |
|
|
512 | (5) |
|
|
517 | (1) |
|
|
518 | (1) |
|
|
519 | (2) |
|
38 Groups of Order 8 and 12: Semidirect Products of Groups |
|
|
521 | (14) |
|
|
521 | (1) |
|
|
522 | (1) |
|
Semi-direct Products of Groups |
|
|
522 | (4) |
|
Groups of Order 12 and p3 |
|
|
526 | (5) |
|
|
531 | (1) |
|
|
531 | (2) |
|
|
533 | (2) |
|
|
535 | (14) |
|
Special Types of Functions: Injections and Surjections |
|
|
536 | (4) |
|
|
537 | (1) |
|
|
538 | (1) |
|
The Importance of the Domain and Codomain |
|
|
539 | (1) |
|
|
540 | (2) |
|
|
542 | (3) |
|
Theorems about Inverse Functions |
|
|
545 | (2) |
|
|
547 | (1) |
|
|
547 | (2) |
|
B Mathematical Induction and the Well-Ordering Principle |
|
|
549 | (20) |
|
|
549 | (1) |
|
The Principle of Mathematical Induction |
|
|
550 | (3) |
|
The Extended Principle of Mathematical Induction |
|
|
553 | (2) |
|
The Strong Form of Mathematical Induction |
|
|
555 | (3) |
|
The Well-Ordering Principle |
|
|
558 | (4) |
|
The Equivalence of the Well-Ordering Principle and the Principles of Mathematical Induction |
|
|
562 | (3) |
|
|
565 | (1) |
|
|
565 | (4) |
Index |
|
569 | |