A Concrete Introduction To Higher Algebra

by Childs, Lindsay N.

• ISBN13: 9780387989990
• ISBN10: 0387989994
• Edition: 2nd
• Format: Paperback
• Copyright: 2000-01-01
• Publisher: Springer Nature

Summary

This book is an informal and readable introduction to higher algebra at the post-calculus level. The concepts of ring and field are introduced through study of the familiar examples of the integers and polynomials. A strong emphasis on congruence classes leads in a natural way to finite groups and finite fields. The new examples and theory are built in a well-motivated fashion and made relevant by many applications--to cryptography, coding, integration, history of mathematics, and especially to elementary and computational number theory. The later chapters include expositions of Rabiin's probabilistic primality test, quadratic reciprocity, and the classification of finite fields. Over 900 exercises, ranging from routine examples to extensions of theory, are found throughout the book; hints and answers for many of them are included in an appendix.

Table of Contents

Introduction	vii
Numbers	1	(7)
Induction	8	(17)
Induction	8	(5)
Another Form of Induction	13	(3)
Well-Ordering	16	(2)
Division Theorem	18	(2)
Bases	20	(3)
Operations in Base a	23	(2)
Euclid's Algorithm	25	(22)
Greatest Common Divisors	25	(2)
Euclid's Algorithm	27	(2)
Bezout's Identity	29	(7)
The Efficiency of Euclid's Algorithm	36	(4)
Euclid's Algorithm and Incommensurability	40	(7)
Unique Factorization	47	(16)
The Fundamental Theorem of Arithmetic	47	(3)
Exponential Notation	50	(5)
Primes	55	(4)
Primes in an Interval	59	(4)
Congruences	63	(13)
Congruence Modulo m	63	(2)
Basic Properties	65	(3)
Divisibility Tricks	68	(3)
More Properties of Congruence	71	(1)
Linear Congruences and Bezout's Identity	72	(4)
Congruence Classes	76	(15)
Congruence Classes (mod m): Examples	76	(4)
Congruence Classes and Z/mZ	80	(2)
Arithmetic Modulo m	82	(4)
Complete Sets of Representatives	86	(2)
Units	88	(3)
Applications of Congruences	91	(27)
Round Robin Tournaments	91	(1)
Pseudorandom Numbers	92	(8)
Factoring Large Numbers by Trial Division	100	(3)
Sieves	103	(2)
Factoring by the Pollard Rho Method	105	(6)
Knapsack Cryptosystems	111	(7)
Rings and Fields	118	(16)
Axioms	118	(6)
Z/mZ	124	(3)
Homomorphisms	127	(7)
Fermat's and Euler's Theorems	134	(21)
Orders of Elements	134	(4)
Fermat's Theorem	138	(3)
Euler's Theorem	141	(4)
Finding High Powers Modulo m	145	(2)
Groups of Units and Euler's Theorem	147	(5)
The Exponent of an Abelian Group	152	(3)
Applications of Fermat's and Euler's Theorems	155	(25)
Fractions in Base a	155	(9)
RSA Codes	164	(5)
2-Pseudoprimes	169	(6)
Trial a-Pseudoprime Testing	175	(2)
The Pollard p -- 1 Algorithm	177	(3)
On Groups	180	(14)
Subgroups	180	(2)
Lagrange's Theorem	182	(3)
A Probabilistic Primality Test	185	(1)
Homomorphisms	186	(3)
Some Nonabelian Groups	189	(5)
The Chinese Remainder Theorem	194	(14)
The Theorem	194	(8)
Products of Rings and Euler's ø-Function	202	(3)
Square Roots of 1 Modulo m	205	(3)
Matrices and Codes	208	(23)
Matrix Multiplication	209	(3)
Linear Equations	212	(2)
Determinants and Inverses	214	(1)
Mn(R)	215	(2)
Error-Correcting Codes, I	217	(7)
Hill Codes	224	(7)
Polynomials	231	(8)
Unique Factorization	239	(14)
Division Theorem	239	(4)
Primitive Roots	243	(2)
Greatest Common Divisors	245	(4)
Factorization into Irreducible Polynomials	249	(4)
The Fundamental Theorem of Algebra	253	(24)
Rational Functions	254	(1)
Partial Fractions	255	(3)
Irreducible Polynomials over R	258	(2)
The Complex Numbers	260	(3)
Root Formulas	263	(6)
The Fundamental Theorem	269	(4)
Integrating	273	(4)
Derivatives	277	(9)
The Derivative of a Polynomial	277	(3)
Sturm's Algorithm	280	(6)
Factoring in Q[x], I	286	(7)
Gauss's Lemma	286	(3)
Finding Roots	289	(2)
Testing for Irreducibility	291	(2)
The Binomial Theorem in Characteristic p	293	(9)
The Binomial Theorem	293	(4)
Fermat's Theorem Revisited	297	(3)
Multiple Roots	300	(2)
Congruences and the Chinese Remainder Theorem	302	(8)
Congruences Modulo a Polynomial	302	(6)
The Chinese Remainder Theorem	308	(2)
Applications of the Chinese Remainder Theorem	310	(13)
The Method of Lagrange Interpolation	310	(3)
Fast Polynomial Multiplication	313	(10)
Factoring in Fp[x] and in Z[x]	323	(23)
Berlekamp's Algorithm	323	(10)
Factoring in Z[x] by Factoring mod M	333	(1)
Bounding the Coefficients of Factors of a Polynomial	334	(4)
Factoring Modulo High Powers of Primes	338	(8)
Primitive Roots	346	(7)
Primitive Roots Modulo m	346	(5)
Polynomials Which Factor Modulo Every Prime	351	(2)
Cyclic Groups and Primitive Roots	353	(10)
Cyclic Groups	353	(3)
Primitive Roots Modulo pe	356	(7)
Pseudoprimes	363	(15)
Lots of Carmichael Numbers	363	(5)
Strong a-Pseudoprimes	368	(4)
Rabin's Theorem	372	(6)
Roots of Unity in Z/mZ	378	(19)
For Which a Is m an a-Pseudoprime?	378	(3)
Square Roots of -- 1 in Z/pZ	381	(1)
Roots of -- 1 in Z/mZ	382	(3)
False Witnesses	385	(3)
Proof of Rabin's Theorem	388	(4)
RSA Codes and Carmichael Numbers	392	(5)
Quadratic Residues	397	(17)
Reduction to the Odd Prime Case	397	(2)
The Legendre Symbol	399	(6)
Proof of Quadratic Reciprocity	405	(2)
Applications of Quadratic Reciprocity	407	(7)
Congruence Classes Modulo a Polynomial	414	(18)
The Ring F[x]/m(x)	414	(4)
Representing Congruence Classes mod m(x)	418	(4)
Orders of Elements	422	(4)
Inventing Roots of Polynomials	426	(2)
Finding Polynomials with Given Roots	428	(4)
Some Applications of Finite Fields	432	(32)
Latin Squares	432	(6)
Error Correcting Codes	438	(12)
Reed--Solomon Codes	450	(14)
Classifying Finite Fields	464	(19)
More Homomorphisms	464	(4)
On Berlekamp's Algorithm	468	(1)
Finite Fields Are Simple	469	(2)
Factoring xpn -- x in Fp[x]	471	(3)
Counting Irreducible Polynomials	474	(3)
Finite Fields	477	(2)
Most Polynomials in Z[x] Are Irreducible	479	(4)
Hints to Selected Exercises	483	(26)
References	509	(4)
Index	513