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 coefficients 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


163
= 262537412640768743.99999999999925 . . .,
which shows that


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 + · · · ,
Previous Page Next Page