__Primes once more (re Kac & Ulam)__

The
__composite____prime__

__Lemma 0__

__Proof__`n`. Either `n` is prime, in which case it has the prime divisor `n`, or it is composite, in which case it has a smaller plural divisor `x` which (because `x` < `n`) has "ex hypothese" a prime divisor that (since `x` divides `n`) is a prime divisor of `n` as well. (End of Proof.)

__Remark__`n`)

〈∀`x`: `x` < `n`: hyp.`x`〉 ⇒ hyp.`n`

Notice in the above proof the absence of separate treatments of "base" and "step". (End of Remark.)

__Lemma 1__

__Proof__`S` be a finite set of prime numbers and consider `k` given by `k` = 1 +〈Π`x`: `x` ∈ `S`: x〉 —because `S` is finite, the product of the numbers in `S` is defined—. By construction, `k` is not divisible by any of the primes in `S` —notice〈∀`x`: `x`∈ `S`: 2≤`x`〉—; by Lemma 0, however, `k` has a prime divisor that is not an element of `S`. (End of Proof.)

(Courtesy A. J. M. van Gasteren)

* *

*

The above has been written down so that we may compare it with how Mark Kac and Stanslaw M. Ulam treat the matter on the 1st page of Chapter 1 of their "Mathematics and Logic":

The following proof, probably still the simplest, asserts the mere existence of arbitrarily large primes. Suppose the number were finite; there would then be a largest prime

p. Consider now the numbern=p! + 1 (p! is read "pfactorial" and equals 1 ∙ 2 ∙ 3 …p). This number is not divisible by any prime up top. If there is no prime betweenpandn, as we have assumed, thennitself would be prime, contrary to our assumption thatpis the largest one.

The authors hesitate between dealing with the number of
primes and the value of primes: the first sentence deals with
their values, the second one mentions their number. The
conclusion of the second sentence is unwarranted: suppose
there were no primes at all, then their number would have been
finite (viz. zero), but there would not have been a largest
prime `p`. (I would like the reader to appreciate that
the argument in our proof of Lemma 1 is perfectly valid when `S` is empty.) The second sentence would have been better had they just written: "Suppose there were a largest prime `p`.".

The third sentence introduces `n`, the fourth sentence
is the first one whose correctness depends on the concept
"prime". Unfortunately, the authors opened their
chapter a little earlier with:

So, 1 is included in their primes, and the conclusion in their fourth sentence is just wrong. [This is another illustration of the fact that including 1 among the prime numbers is an unfortunate interface.]1.

The Infinity of Primes

Among the so-called natural numbers (1, 2, 3, and so on) are some that are divisible only by 1 and by themselves; these are called theprime numbers. The prime numbers are the building blocks of all the numbers in the sense that every natural number is the product of powers of the primes that divide it. For instance 60 = 2^{2}∙3∙5. The first several primes are 1, 2, 3, 5, 7, 11, 13, 17. It can be asked whether the series goes on forever, or, in other words, whether there is a largest prime. The answer is that there is no largest prime. This has been known since the golden age of Greece. It was proved by Euclid in the 3rd century B.C. His argument is as clear and fresh today as ever.

The fifth sentence is supposed to conclude the proof, but
it is very elliptic as it does not mention which property of
prime numbers should justify the conclusion. It looks as if
we are invited to conclude from the fact that none of the
numbers between `p` and `n` is prime that none of
these numbers divides `n`, and I hope that we are not supposed to use that "Every natural number is the product of [positive] powers of the primes that divide it", for otherwise we could apply the possibility of that factorization to `n` directly and conclude, without the
assumption that `p` was the largest prime,
because `n` ≥ 2 the existence of a prime larger
than `p`. The last step of the quoted
proof needs a possibly unstated and in any case unproven
lemma (whose proof almost certainly requires mathematical
induction). What an awful mess! And that in a book with the
title "Mathematics and Logic"!

Now we are at it, I draw the reader's attention to the following sentence from the second quotation:

However, the answer to the first question is "yes", and to the second one "no"."It can be asked whether the series [of primes] goes on forever, or, in other words, whether there is a largest prime."

Mark Kac and Stanislaw M. Ulam, "Mathematics and Logic", originally published: New York: Praeger, 1968, in series: Brittanica perspective. Dover Publications, Mineola, NY, 1992.

Austin, 17 March 1995

prof. dr. Edsger W. Dijkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712-1188

USA

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712-1188

USA