ABSTRACT
This chapter covers the basics of number theory. Number theory, a subject with a long and rich history, has become increasingly important because of its applications to computer science and cryptography. The chapter covers the core topics of number theory, such as divisibility, radix representations, greatest common divisors, primes, factorization, congruences, dio-phantine equations, and continued fractions. It describes the algorithms for finding greatest common divisors, large primes, and factorizations of integers. There are many famous problems in number theory, including some that have been solved only recently, such as Fermat's last theorem, and others that have eluded resolution, such as the Goldbach conjecture. New discoveries in number theory, such as new large primes, are being made at an increasingly fast pace. The chapter also describes the current state of knowledge and provides pointers to Internet sources where the latest facts can be found.
