Number Theory 23

decay in the density as one moves to higher numbers. Since theorem 17 shows that there

are large primeless intervals, we should expect to find increasing white patches, without

any blue lines, if the figure were continued to larger numbers.

In contrast to the previous result, let us now provide a lower bound on the number of

prime numbers. Define that a positive integer r is square-free if it is not a multiple of any

square number bigger than 1; equivalently, by exercise 3.12, a positive integer is square-

free if all the primes in its prime factorization have exponent 1.

Theorem 18 (Erd

˝

os). The prime-counting function π has a lower bound provided by the

inequality

log

2

(n)

2

≤ π(n).

Proof. Every natural number can be factored as rs

2

, where r is square-free, as the reader

will verify in exercise 3.13. How many square-free numbers are there less than n? Well,

every square-free number is a product of distinct primes, and so it is determined by the

set of primes that divide it. So the number of square-free numbers up to n will be at most

2

π(n)

, which is the number of sets of primes up to n. Second, the number of squares up to

n is at most

√

n, since if s

2

≤ n then s ≤

√

n, and s

2

is determined by s. So the number

of numbers up to n having the form rs

2

, where r is square-free, is at most 2

π(n)

√

n. Since

there are n positive integers less than or equal to n, we conclude that

n ≤ 2

π(n)

√

n.

Dividing both sides by

√

n leads to

√

n ≤ 2

π(n)

, and then taking the logarithm (base 2)

enables us to conclude that

log

2

(

√

n) ≤ log

2

(2

π(n)

),

which amounts to the inequality

1

2

log

2

(n) ≤ π(n),

as desired.

An arithmetic progression is a sequence of numbers of the form p, p + e, p + 2e, p + 3e,

and so on. Two numbers are relatively prime if they have no nontrivial common factor.

Theorem 19. There are arbitrarily long arithmetic progressions consisting of relatively

prime numbers.

Proof. Fix any number d, and let e = d!, the factorial of it. Let p be a prime number larger

than e, and consider the numbers

pp+ ep+ 2ep+ 3e ··· p + (d − 1)e,