Introduction to Number Theory

Truman State University, Kirksville, Missouri, USA Truman State University, Kirksville, Missouri, USA

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.