32 1. Elementary Prime Number Theory, I

form α·n!+1. Letting l → ∞, we obtain infinitely many composite numbers

of this form.

Notes

Most of the proofs discussed for the infinitude of the primes may be found

in [Dic66, Chapter XVIII] or [Nar00, §1.1]. For other compilations, see

[Rib96, Chapter 1], [FR07, Chapter 3], and [Moh79]. An amusing ver-

sion of Euclid’s proof, couched in the language of nonstandard analysis,

is presented in [Gol98, pp. 57–58]. Additional elementary proofs of the

stronger result that

∑

1/p diverges may be found in [Bel43], [Mos58], and

the survey [VE80].

The following result of Matijasevich and Putnam provides an interest-

ing contrast to Goldbach’s theorem (Theorem 1.9): There is a polynomial

with integral coeﬃcients such that the set of primes coincides with the set

of positive values assumed by this polynomial, as the variables range over

the nonnegative integers. (An explicit example of such a polynomial, in 26

variables, was produced by Jones et al. [JSWW76].) Yet upon inspection

we realize we are once again looking at a result that properly belongs not to

number theory but to computability theory (or logic); an analogous state-

ment is true if we replace the set of primes with any listable set. Here a

set of positive integers S is called listable if there is a computer program

which, when left running forever, outputs precisely the elements of S. A

very approachable introduction to this circle of ideas is Matijasevich’s arti-

cle [Mat99]; for complete details see [Mat93].

In connection with the results of §8, we cannot resist pointing out the

remarkable identity

eπ

√

163

= 262537412640768743.99999999999925 . . .,

which shows that

eπ

√

163

is very nearly an integer. We sketch the explana-

tion, which comes from the theory of modular functions; for details one may

consult [Cox89, §11]. Every lattice L ⊂ C has a so-called j-invariant j(L),

and j(L1) = j(L2) precisely when L1 and L2 are homothetic, i.e., when one

can be obtained from the other by rotation and scaling. We view j as a

function on the upper half-plane {z ∈ C : (z) 0} by defining j(τ) as

j(L), where L is the lattice spanned by 1 and τ. It turns out that j is then

holomorphic on the upper half-plane. Moreover, since 1 and τ determine the

same lattice as 1 and τ + 1, we have j(τ) = j(τ + 1). This shows that j(τ)

is holomorphic as a function of q =

e2πiτ

in the punctured disc 0 |q| 1,

and so j has a Laurent expansion. It turns out that this expansion starts

j(τ) =

1

q

+ 744 + 196884q + · · · ,