The Infinitude of Primes

The two most striking characteristics of the sequence of primes is that there are many of them but that their density is rather slim. From Euclid’s theorem (Theorem 2.3.1) there are infinitely many primes; in fact, there are infinitely many in any nontrivial arithmetic sequence of integers. This latter fact was proved by Dirichlet and is known as Dirichlet’s theorem. As mentioned before, if x is a natural number and π(x) represents the number of primes less than or equal to x, then asymptotically this function behaves like the function x/ln x . This result is known as the prime number theorem. Besides being a startling result, the proof of the prime number theorem, done independently by Hadamard and de la Vallée Poussin, became the genesis for analytic number theory. In this chapter we will discuss various aspects of the infinitude of primes. The prime number theorem will be introduced in the next chapter.