Table of Contents

1 Numbers.- 2 Induction.- A. Induction.- B. Another Form of Induction.- C. Well-Ordering.- D. Division Theorem.- E. Bases.- F. Operations in Base a.- 3 Euclid’s Algorithm.- A. Greatest Common Divisors.- B. Euclid’s Algorithm.- C. Bezout’s Identity.- D. The Efficiency of Euclid’s Algorithm.- E. Euclid’s Algorithm and Incommensurability.- 4 Unique Factorization.- A. The Fundamental Theorem of Arithmetic.- B. Exponential Notation.- C. Primes.- D. Primes in an Interval.- 5 Congruences.- A. Congruence Modulo m.- B. Basic Properties.- C. Divisibility Tricks.- D. More Properties of Congruence.- E. Linear Congruences and Bezout’s Identity.- 6 Congruence Classes.- A. Congruence Classes (mod m): Examples.- B. Congruence Classes and ?/m?.- C. Arithmetic Modulo m.- D. Complete Sets of Representatives.- E. Units.- 7 Applications of Congruences.- A. Round Robin Tournaments.- B. Pseudorandom Numbers.- C. Factoring Large Numbers by Trial Division.- D. Sieves.- E. Factoring by the Pollard Rho Method.- F. Knapsack Cryptosystems.- 8 Rings and Fields.- A. Axioms.- B. ?/m?.- C. Homomorphisms.- 9 Fermat’s and Euler’s Theorems.- A. Orders of Elements.- B. Fermat’s Theorem.- C. Euler’s Theorem.- D. Finding High Powers Modulo m.- E. Groups of Units and Euler’s Theorem.- F. The Exponent of an Abelian Group.- 10 Applications of Fermat’s and Euler’s Theorems.- A. Fractions in Base a.- B. RSA Codes.- C. 2-Pseudoprimes.- D. Trial a-Pseudoprime Testing.- E. The Pollard p — 1 Algorithm.- 11 On Groups.- A. Subgroups.- B. Lagrange’s Theorem.- C. A Probabilistic Primality Test.- D. Homomorphisms.- E. Some Nonabelian Groups.- 12 The Chinese Remainder Theorem.- A. The Theorem.- B. Products of Rings and Euler’s ?-Function.- C. Square Roots of 1 Modulo m.- 13 Matricesand Codes.- A. Matrix Multiplication.- B. Linear Equations.- C. Determinants and Inverses.- D. Mn(R).- E. Error-Correcting Codes, I.- F. Hill Codes.- 14 Polynomials.- 15 Unique Factorization.- A. Division Theorem.- B. Primitive Roots.- C. Greatest Common Divisors.- D. Factorization into Irreducible Polynomials.- 16 The Fundamental Theorem of Algebra.- A. Rational Functions.- B. Partial Fractions.- C Irreducible Polynomials over ?.- D. The Complex Numbers.- E. Root Formulas.- F. The Fundamental Theorem.- G. Integrating.- 17 Derivatives.- A. The Derivative of a Polynomial.- B. Sturm’s Algorithm.- 18 Factoring in ?[x], I.- A. Gauss’s Lemma.- B. Finding Roots.- C. Testing for Irreducibility.- 19 The Binomial Theorem in Characteristic p.- A. The Binomial Theorem.- B. Fermat’s Theorem Revisited.- C. Multiple Roots.- 20 Congruences and the Chinese Remainder Theorem.- A. Congruences Modulo a Polynomial.- B. The Chinese Remainder Theorem.- 21 Applications of the Chinese Remainder Theorem.- A. The Method of Lagrange Interpolation.- B. Fast Polynomial Multiplication.- 22 Factoring in Fp[x] and in ?[x].- A. Berlekamp’s Algorithm.- B. Factoring in ?[x] by Factoring mod M.- C. Bounding the Coefficients of Factors of a Polynomial.- D. Factoring Modulo High Powers of Primes.- 23 Primitive Roots.- A. Primitive Roots Modulo m.- B. Polynomials Which Factor Modulo Every Prime.- 24 Cyclic Groups and Primitive Roots.- A. Cyclic Groups.- B. Primitive Roots Modulo pe.- 25 Pseudoprimes.- A. Lots of Carmichael Numbers.- B. Strong a-Pseudoprimes.- C. Rabin’s Theorem.- 26 Roots of Unity in ?/m?.- A. For Which a Is m an a-Pseudoprime?.- B. Square Roots of ?1 in ?/p?.- C. Roots of ?1 in ?/m?.- D. False Witnesses.- E. Proof of Rabin’s Theorem.- F. RSA Codes andCarmichael Numbers.- 27 Quadratic Residues.- A. Reduction to the Odd Prime Case.- B. The Legendre Symbol.- C. Proof of Quadratic Reciprocity.- D. Applications of Quadratic Reciprocity.- 28 Congruence Classes Modulo a Polynomial.- A. The Ring F[x]/m(x).- B. Representing Congruence Classes mod m(x).- C. Orders of Elements.- D. Inventing Roots of Polynomials.- E. Finding Polynomials with Given Roots.- 29 Some Applications of Finite Fields.- A. Latin Squares.- B. Error Correcting Codes.- C. Reed-Solomon Codes.- 30 Classifying Finite Fields.- A. More Homomorphisms.- B. On Berlekamp’s Algorithm.- C. Finite Fields Are Simple.- D. Factoring xpn — x in Fp[x].- E. Counting Irreducible Polynomials.- F. Finite Fields.- G. Most Polynomials in Z[x] Are Irreducible.- Hints to Selected Exercises.- References.

Promotional Information

2nd edition

Reviews

From the reviews: "The user-friendly exposition is appropriate for the intended audience. Exercises often appear in the text at the point they are relevant, as well as at the end of the section or chapter. Hints for selected exercises are given at the end of the book. There is sufficient material for a two-semester course and various suggestions for one-semester courses are provided. Although the overall organization remains the same in the second edition¿Changes include the following: greater emphasis on finite groups, more explicit use of homomorphisms, increased use of the Chinese remainder theorem, coverage of cubic and quartic polynomial equations, and applications which use the discrete Fourier transform." MATHEMATICAL REVIEWS