7. Prime-producing formulas 13

Proof. We use the theorem that a Dedekind domain with finitely many

nonzero prime ideals is a principal ideal domain (see, e.g., [Lor96, Propo-

sition III.2.12]) and thus also a unique factorization domain. The ring of

integers OK of a number field K is always a Dedekind domain; consequently,

if K does not possess unique factorization, then OK has infinitely many

nonzero prime ideals. Each such prime ideal lies above a rational prime p,

and for each prime p there are at most [K : Q] prime ideals lying above it.

It follows that there are infinitely many primes p, provided that there is a

single number field K for OK does not possess unique factorization.

And there is: If K = Q(

√which

−5), then

6 = (1 +

√

−5)(1 −

√

−5)

is a well-known instance of the failure of unique factorization in OK =

Z[

√

−5].

7. Prime-producing formulas

A mathematician is a conjurer who gives away his se-

crets. – J. H. Conway

Now that we know there are infinitely many primes, the next question is:

Where are they hiding? Or, to ask a question that has ensnared many

who have flirted with number theory: Is there a formula for producing

primes? This line of inquiry, as natural as it seems, has not been very

productive.

The following 1952 result of Sierpi´ nski [Sie52] is representative of many

in this subject. Let pn denote the nth prime number. Define a real number

ξ by putting

ξ :=

∞

n=1

pn10−2n

= 0.02030005000000070000000000000011 . . ..

Theorem 1.7. We have

pn =

102n

ξ −

102n−1 102n−1

ξ .

This is, in the literal sense, a formula for primes. But while it may

have some aesthetic merit, it must be considered a complete failure from

the standpoint of utility; determining the number ξ seems to require us

to already know the sequence of primes. A similar criticism can be leveled

against a result of Mills [Mil47], which asserts the existence of a real number

A 1 with the property that

A3n

is prime for each natural number n.

A more surprising way of generating primes was proposed by J. H. Con-

way [Con87]. Consider the following list of 14 fractions: