English | Español

Try our Free Online Math Solver!

Online Math Solver












Please use this form if you would like
to have this math solver on your website,
free of charge.

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

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

0.3 Call a set of positive integers a PC-set if it has the property that
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 = a2b3 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 .

Prev Next