You are here

Introduction to Number Theory

Martin Erickson and Anthony Vazzana
Publication Date: 
Number of Pages: 
Discrete Mathematics and Its Applications
[Reviewed by
Underwood Dudley
, on

This is a text for advanced undergraduates. It is notable for including everything that anyone would expect to find in an elementary number theory text, and more. For example, besides chapters on analytic number theory and elliptic curves, there is an outline of the resolution of Hilbert’s tenth problem. Continued fractions get a chapter, the gaussian integers are developed to answer the question of which integers are the sums of two squares, the Dirichlet convolution, of which I have always been fond, is given its due, and Hadamard matrices make an appearance.

Of course, this makes for a long book, more than 520 pages, that could not possibly be covered in a semester. As the authors point out, chapters 1–9, omitting chapter 4 on cryptography, give the basics, and then some, in 320 pages.

A feature of the book of which, for good or ill, prospective users should be aware is the inclusion of code, for both Mathematica and Maple, for various algorithms. Reading it did very little for me and , since the code can be found on the authors’ website, students would not have to retype it. Devotees of one or other of the programs may well feel differently.

The exposition is straightforward, written in good mathematical prose without distractions or infelicities. There is a good selection of exercises at the end of each of the five to ten sections in each chapter but no answers or hints at the back of the book, not even to problems whose numbers are congruent to 7 (mod 8). I would have liked to see more examples, but the authors are not aiming at weak students (who will find the book slow going, written as it is in lemma-proposition-theorem-proof style) and making the book longer would be a mistake.

The book is remarkably free of errors and misprints, for which the authors and their editor deserve great credit. Reviewers, however, are entitled to two free shots: there is a grammatical error on page 346, line 3, and on page 80 Lagrange is given a Spanish flavor (“Joseph-Luis”).

The book is pleasing to the eye except for the tables, which have too many heavy lines. The authors are to be congratulated for avoiding that uncouth usage, which unfortunately may be spreading, of “dt” in integrals.

It contains no color pictures, no sidebars, its margins are of the standard size, and though the authors include “real-life” applications, they do not claim that number theory will lead to lucrative careers.

Erickson and Vazzana have written an admirable text.

Woody Dudley’s number theory text was published forty years ago. The field has changed since then, slightly.

Core Topics

What is number theory?
The natural numbers
Mathematical induction

Divisibility and Primes
Basic definitions and properties
The division algorithm
Greatest common divisor
The Euclidean algorithm
Linear Diophantine equations
Primes and the fundamental theorem of arithmetic

Residue classes
Linear congruences
Application: Check digits and the ISBN system
Fermat’s theorem and Euler’s theorem
The Chinese remainder theorem
Wilson’s theorem
Order of an element mod n
Existence of primitive roots
Application: Construction of the regular 17-gon

Monoalphabetic substitution ciphers
The Pohlig–Hellman cipher
The Massey–Omura exchange
The RSA algorithm

Quadratic Residues
Quadratic congruences
Quadratic residues and nonresidues
Quadratic reciprocity
The Jacobi symbol
Application: Construction of tournaments
Consecutive quadratic residues and nonresidues
Application: Hadamard matrices

Further Topics

Arithmetic Functions
Perfect numbers
The group of arithmetic functions
Möbius inversion
Application: Cyclotomic polynomials
Partitions of an integer

Large Primes
Prime listing, primality testing, and prime factorization
Fermat numbers
Mersenne numbers
Prime certificates
Finding large primes

Continued Fractions
Finite continued fractions
Infinite continued fractions
Rational approximation of real numbers
Periodic continued fractions
Continued fraction factorization

Diophantine Equations
Linear equations
Pythagorean triples
Gaussian integers
Sums of squares
The case n = 4 in Fermat’s last theorem
Pell’s equation
Continued fraction solution of Pell’s equation
The abc conjecture

Advanced Topics

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

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

Logic and Number Theory
Solvable and unsolvable equations
Diophantine equations and Diophantine sets
Positive values of polynomials
Logic background
The negative solution of Hilbert’s tenth problem
Diophantine representation of the set of primes

APPENDIX A: Mathematica Basics

APPENDIX B: Maple Basics

APPENDIX C: Web Resources

APPENDIX D: Notation



Notes appear at the end of each chapter.