Introduction to Number Theory is a classroom-tested, student-friendly text that covers a diverse array of number theory topics, from the ancient Euclidean algorithm for finding the greatest common divisor of two integers to recent developments such as cryptography, the theory of elliptic curves, and the negative solution of Hilbert's tenth problem. The authors illustrate the connections between number theory and other areas of mathematics, including algebra, analysis, and combinatorics. They also describe applications of number theory to real-world problems, such as congruences in the ISBN system, modular arithmetic and Euler's theorem in RSA encryption, and quadratic residues in the construction of tournaments. Ideal for a one- or two-semester undergraduate-level course, this Second Edition: * Features a more flexible structure that offers a greater range of options for course design * Adds new sections on the representations of integers and the Chinese remainder theorem * Expands exercise sets to encompass a wider variety of problems, many of which relate number theory to fields outside of mathematics (e.g., music) * Provides calculations for computational experimentation using SageMath, a free open-source mathematics software system, as well as Mathematica(R) and Maple(TM), online via a robust, author-maintained website * Includes a solutions manual with qualifying course adoption By tackling both fundamental and advanced subjects-and using worked examples, numerous exercises, and popular software packages to ensure a practical understanding-Introduction to Number Theory, Second Edition instills a solid foundation of number theory knowledge.
Introduction What is number theory? The natural numbers Mathematical induction Notes The Peano axioms Divisibility Basic definitions and properties The division algorithm Representations of integers Greatest Common Divisor Greatest common divisor The Euclidean algorithm Linear Diophantine equations Notes Euclid The number of steps in the Euclidean algorithm Geometric interpretation of the equation ax + by = c Primes The sieve of Eratosthenes The fundamental theorem of arithmetic Distribution of prime numbers Notes Eratosthenes Nonunique factorization and Fermat's last theorem Congruences Residue classes Linear congruences Application: Check digits and the ISBN-10 system The Chinese remainder theorem Special Congruences Fermat's theorem Euler's theorem Wilson's theorem Notes Leonhard Euler Primitive Roots Order of an element mod n Existence of primitive roots Primitive roots modulo composites Application: Construction of the regular 17-gon Notes Groups Straightedge and compass constructions Cryptography Monoalphabetic substitution ciphers The Pohlig-Hellman cipher The Massey-Omura exchange The RSA algorithm Notes Computing powers mod p RSA cryptography Quadratic Residues Quadratic congruences Quadratic residues and nonresidues Quadratic reciprocity The Jacobi symbol Notes Carl Friedrich Gauss Applications of Quadratic Residues Application: Construction of tournaments Consecutive quadratic residues and nonresidues Application: Hadamard matrices Sums of Squares Pythagorean triples Gaussian integers Factorization of Gaussian integers Lagrange's four squares theorem Notes Diophantus Further Topics in Diophantine Equations The case n = 4 in Fermat's last theorem Pen's equation The abc conjecture Notes Pierre de Fermat The p-adic numbers Continued Fractions Finite continued fractions Infinite continued fractions Rational approximation of real numbers Notes Continued fraction expansion of e Continued fraction expansion of tan x Srinivasa Ramanujan Continued Fraction Expansions of Quadratic Irrationals Periodic continued fractions Continued fraction factorization Continued fraction solution of Pen's equation Notes Three squares and triangular numbers History of Pen's equation Arithmetic Functions Perfect numbers The group of arithmetic functions Mobius inversion Application: Cyclotomic polynomials Partitions of an integer Notes The lore of perfect numbers Pioneers of integer partitions Large Primes Fermat numbers Mersenne numbers Prime certificates Finding large primes Analytic Number Theory Sum of reciprocals of primes Orders of growth of functions Chebyshev's theorem Bertrand's postulate The prime number theorem The zeta function and the Riemann hypothesis Dirichlet's theorem Notes Paul Erdos Elliptic Curves Cubic curves Intersections of lines and curves The group law and addition formulas Sums of two cubes Elliptic curves mod p Encryption via elliptic curves Elliptic curve method of factorization Fermat's last theorem Notes Projective space Associativity of the group law
