This introductory number theory textbook has a particular emphasis on connections to cryptology. The cryptologic material arising naturally out of the ambient number theory. The main cryptologic applications — being the RSA cryptosystem, Diffie-Hellman key exchange, and the ElGamal cryptosystem — come out so naturally from considerations of Euler's Theorem, primitive roots, and indices that it renders quite ironic G.H. Hardy's assertion of the purity and eternal inapplicability of number theory.
- In this chapter, we present three basic tools that will often be used in proving properties of the integers. We start with a very important property of integers called the well-ordering principle. We then state what is known as the pigeonhole principle, and then we proceed to present an important method called mathematical induction.
- Primes are the atoms out of which the more complicated, composite integers (the molecules, in this metaphor) are built. In this chapter we study some of their basic properties, prove the aptly named Fundamental Theorem of Arithmetic, and go on to Wilson’s Theorem.