*Core Topics *

**Introduction **

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

**Congruences **

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

**Cryptography **

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 **

**References **

**Index**

*Notes appear at the end of each chapter.*