Yet Another Introductory Number Theory Textbook – Cryptology Emphasis (Poritz)

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.

Well-Ordering and Division

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.

The Euclidean Algorithm

In this section, we describe a systematic method that determines the greatest common divisor of two integers, due to Euclid and thus called the Euclidean algorithm. Now to the Euclidean algorithm in its general form, which basically states that the greatest common divisor of two integers is the last non-zero remainder of successive divisions.

The full version of this theorem, with the ’s and , is called the extended Euclidean Algorithm, while a simpler version without those coefficients is know as Euclidean Algorithm.

The attentive reader will have seen that We did not actually prove that the ’s and ’s can be used, as claimed, to write the as a linear combination of and . This proof is left as an exercise, below.

Linear Congruences

Because congruence is analogous to equality, it is natural to ask about the analogues of linear equations, the simplest equations one can solve in algebra, but using congruence rather than equality. In this section, we discuss linear congruences of one variable and their solutions.

The Chinese Remainder Theorem

In this section, we discuss solutions of systems of congruences having different moduli. An example of this kind of systems is the following: find a number that leaves a remainder of when divided by , a remainder of when divided by three, and a remainder of when divided by . We shall see that there is a systematic way of solving this kind of system.