Chapter 1

Elementary Prime

Number Theory, I

Prime numbers are more than any assigned multitude of

prime numbers. – Euclid

No prime minister is a prime number – A. Plantinga

1. Introduction

Recall that a natural number larger than 1 is called prime if its only positive

divisors are 1 and itself, and composite otherwise. The sequence of primes

begins

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,...

Few topics in number theory attract more attention, popular or professional,

than the theory of prime numbers. It is not hard to see why. The study

of the distribution of the primes possesses in abundance the very features

that draw so many of us to mathematics in the first place: intrinsic beauty,

accessible points of entry, and a lingering sense of mystery embodied in

numerous unpretentious but infuriatingly obstinate open problems.

Put

π(x) := #{p ≤ x : p prime}.

Prime number theory begins with the following famous theorem from antiq-

uity:

Theorem 1.1. There are infinitely many primes, i.e., π(x) → ∞ as x → ∞.

1

http://dx.doi.org/10.1090/mbk/068/01