Number Theory: An Introduction to Mathematics

IX The Number of Prime Numbers................................

1 FindingtheProblem

It was already shown in Euclid’sElements(Book IX, Proposition 20) that there are
infinitely many prime numbers. The proof is a model of simplicity: letp 1 ,...,pnbe
any finite set of primes and consider the integerN=p 1 ···pn+1. ThenN>1and
each prime divisorpofNis distinct fromp 1 ,...,pn,sincep=pjwould imply that
pdividesN−p 1 ···pn=1. It is worth noting that the same argument applies if we
takeN=pα 11 ···pαnn+1, with any positive integersα 1 ,...,αn.
Euler (1737) gave an analytic proof of Euclid’s result, which provides also quanti-
tative information about the distribution of primes:

Proposition 1The series

∑

p^1 /p, where p runs through all primes, is divergent.

Proof For any primepwe have

( 1 − 1 /p)−^1 = 1 +p−^1 +p−^2 +···

and hence
∏

p≤x

( 1 − 1 /p)−^1 =

∏

p≤x

( 1 +p−^1 +p−^2 +···)>

∑

n≤x

1 /n,

since any positive integern≤xis a product of powers of primesp≤x.Since

∑

n≤x

1 /n>

∑

n≤x

∫n+ 1

n

dt/t>logx,

it follows that
∏

p≤x

( 1 − 1 /p)−^1 >logx.

On the other hand, since the representation of any positive integer as a product of
prime powers isunique,

∏

p≤x

( 1 − 1 /p^2 )−^1 =

∏

p≤x

( 1 +p−^2 +p−^4 +···)≤

∑∞

n= 1

1 /n^2 =:S,

W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext,
DOI: 10.1007/978-0-387-89486-7_9, © Springer Science + Business Media, LLC 2009

363