This chapter begins with elementary results concerning Euclidean division and the Euclidean algorithm. We show that the algorithm’s complexity, measured in division steps, has logarithmic growth.

Gently introducing the reader to analytic methods in number theory, we present a proof of the divergence of the Euler series that sums the reciprocals of prime numbers. This not only provides an elegant analytic proof of the infinitude of primes but also offers insight into their distribution.

We then turn to classical arithmetic functions and derive recursive formulas for the partition function, culminating in a complete proof of Euler’s pentagonal number theorem.

This chapter also includes the first of three proofs in this book of Gauss’s theorema fundamentale, the law of quadratic reciprocity, which reveals a remarkable symmetry in the solvability of quadratic congruences modulo two distinct odd primes.

These theoretical foundations underpin practical applications, including the Miller–Rabin primality test – a probabilistic method for identifying prime numbers – and RSA encryption, a cornerstone of modern cryptography that relies on the computational difficulty of factoring large integers.