Integer and Polynomial Algebra

This book is a concrete introduction to abstract algebra and number theory. Starting from the basics, it develops the rich parallels between the integers and polynomials, covering topics such as Unique Factorization, arithmetic over quadratic number fields, the RSA encryption scheme, and finite fields. In addition to introducing students to the rigorous foundations of mathematical proofs, the authors cover several specialized topics, giving proofs of the Fundamental Theorem of Algebra, the transcendentality of (e), and Quadratic Reciprocity Law. The book is aimed at incoming undergraduate students with a strong passion for mathematics. Contents 8 Preface 10 Chapter 1. The Integers 14 1.1. Basic Properties 14 1.2. Well Ordering Principle 18 1.3. Primes 20 1.4. Many Primes 23 1.5. Euclidean Algorithm 25 1.6. Factoring Integers 29 1.7. Irrational Numbers 32 1.8. Unique Factorization in More General Rings 34 Notes on Chapter 1 42 Chapter 2. Modular Arithmetic 44 2.1. Linear Equations 44 2.2. Congruences 47 2.3. The Ring \bZ_{n} 49 2.4. Equivalence Relations 53 2.5. Chinese Remainder Theorem 55 2.6. Congruence Equations 58 2.7. Fermat’s Little Theorem 61 2.8. Euler’s Theorem 63 2.9. More on Euler’s Phi Function 65 2.10. Primitive Roots 67 Notes on Chapter 2 71 Chapter 3. Diophantine Equations and Quadratic Number Domains 72 3.1. Pythagorean Triples 73 3.2. Fermat’s Equation for n=4 76 3.3. Quadratic Number Domains 78 3.4. Pell’s Equation 83 3.5. The Gaussian Integers 85 3.6. Quadratic Reciprocity 90 Notes on Chapter 3 96 Chapter 4. Codes and Factoring 98 4.1. Codes 98 4.2. The Rivest-Shamir-Adelman Scheme 99 4.3. Primality Testing 102 4.4. Factoring Algorithms 104 Notes on Chapter 4 106 Chapter 5. Real and Complex Numbers 108 5.1. Real Numbers 108 5.2. Complex Numbers 111 5.3. Polar Form 114 5.4. The Exponential Function 117 5.5. Fundamental Theorem of Algebra 119 5.6. Real Polynomials 122 Notes on Chapter 5 124 Chapter 6. The Ring of Polynomials 128 6.1. Preliminaries on Polynomials 128 6.2. Unique Factorization for Polynomials 131 6.3. Irreducible Polynomials in \bZ[x] 134 6.4. Eisenstein’s Criterion 136 6.5. Factoring Modulo Primes 138 6.6. Algebraic Numbers 141 6.7. Transcendental Numbers 143 6.8. Sturm’s Algorithm 148 6.9. Symmetric Functions 151 6.10. Cubic Polynomials 156 Notes on Chapter 6 160 Chapter 7. Finite Fields 162 7.1. Arithmetic Modulo a Polynomial 162 7.2. An Eight-Element Field 165 7.3. Fermat’s Little Theorem for Finite Fields 168 7.4. Characteristic 170 7.5. Algebraic Elements 172 7.6. Finite Fields 174 7.7. Automorphisms of \bF_{p^{d}} 177 7.8. Irreducible polynomials of all degrees 181 7.9. Factoring Algorithms for Polynomials 187 7.10. Factoring Rational Polynomials 189 Notes on Chapter 7 193 Bibliography 194 Index 196