Introduction to Analytic Number Theory

0.3 The infinitude of primes

We conclude this chapter with a proof of the infinitude of primes, a result
first proved some two thousand years ago by Euclid.

Theorem 0.2. There are infinitely many primes.

Proof. We give here a somewhat nonstandard proof, which, while not as
short as some other proofs, has a distinctly analytic flavor. It is based on
the following lemma, which is of interest in its own right.

Lemma 0.3. Let be a finite set of primes, let



i.e., is the set of positive integers all of whose prime factors belong to
the set P (note that ), and let



Then there exist constants c and (depending on P) such that


Proof. Note that



and that by the Fundamental Theorem of Arithmetic each element in
corresponds to a unique k-tuple of nonnegative integers. Thus,

Now note that the inequality implies
for each i. Hence, for each there are at most
[ log x/ log 2] + 1 choices, and the number of tuples counted in
is therefore

If we now restrict x by x ≥ 2, then [ log x/ log 2] + 1 ≤ 2 log x/ log 2, so the
above becomes

This gives the asserted bound for with c = (2/ log 2)^k and .

With this lemma at hand, the infinitude of primes follows easily: If
there were only finitely many primes, then we could apply the lemma with
P equal to the set of all primes and, consequently, the set of all positive
integers, so that = [x] for all x ≥1. But the lemma would give
the bound for all x ≥2 with some constant c, and since
tends to zero as x → ∞, this is incompatible with the equality
= [x].

0.4 Exercises

0.1 Show that there exist arbitrarily large intervals that are free of primes,
i.e., for every positive integer k there exist k consecutive positive integers
none of which is a prime.

0.2 Let be a polynomial with integer coefficients and
of degree k ≥1. Show that p(n) is composite for infinitely many integers
n.

Remark: With "composite" replaced by "prime", the question becomes
a famous problem that is open (in general) for polynomials of
degree at least 2. For example, it is not known whether there are
infinitely many primes of the form p(n) = n² + 1.

0.3 Call a set of positive integers a PC-set if it has the property that
any pair of distinct elements of the set is coprime. Given x ≥ 2,
let , A is a PC-set }, i.e., N(x) is the
maximal number of integers with the PC property that one can t
into the interval [2, x]. Prove that N(x) is equal to π(x), the number
of primes ≤ x.

0.4 A positive integer n is called squarefull if it satisfies (* ) .
(Note that n = 1 is squarefull according to this definition, since 1 has
no prime divisors and the above implication is therefore trivially true.)

(i) Show that n is squarefull if and only if n can be written in the
form n = a²b³ with a, b ∈ N.

(ii) Find a similar characterization of "k-full" integers, i.e., integers
n ∈ N that satisfy (* ) with 2 replaced by k (where k ≥ 3).

0.5 Let be a finite set of primes, let



i.e., is the set of positive integers all of whose prime factors belong
to the set P (note that 1 2 ), and let



In Lemma 0.3 we showed that for a suitable constant
(depending on the set P, but not on x) and for all sufficiently
large x, say . Prove that a bound of the same type holds in the
other direction, i.e., there exist constants and , depending on
P, such that holds for all .