FOM: reply to Torkel on proof of infinity of primes

[Neil Tennant]

This is in further responses to Torkel's claim that the proof of the
infinity of primes does not make use of certain assumptions. It could
be argued that the `standard' method he alluded to is that of the
first proof of the Theorem below (that there are infinitely many primes).

The existence of the alternative, second proof does not impugn the
method of the first proof.

Lemma 1. For every n, for every set of n natural numbers, there is a
prime not in that set.

Proof. Let k1,...,kn be the n numbers in question. Consider
(k1*...*kn)+1.  If (k1*...*kn)+1 is prime, we are done, since
(k1*...*kn)+1 is greater than, hence distinct from, each ki.  If
(k1*...*kn)+1 is not prime, then it has a prime factor.  Let such a
factor be p. p cannot be any ki, since if it were it would leave
remainder 1 when divided into (k1*...*kn)+1.

Lemma 2. For every n, there is some prime > n.

Proof. Consider n!+1. If n!+1 is prime, we are done, since n!+1>n.  But
if n!+1 is not prime, then it has a prime factor. Let such a factor be
p. p cannot be less than or equal to n, since if it were it would
leave remainder 1 when divided into n!+l. So p>n.  

Theorem. For every prime p, there is some prime > p.

First proof. Take an arbitrary prime p. Let k1,...,kn=p be all the
primes less than or equal to p. Consider (k1*...*kn)+1 and apply the
method of the proof of Lemma 1. [NOTE THAT IN THIS PROOF ONE *IS*
USING THE PRIMALITY OF EACH ki IN ORDER TO CONCLUDE THAT ANY PRIME
FACTOR OF (k1*...kn)+1 WOULD BE > p.]

Second proof. Take an arbitrary prime number p. Consider p!+1 and
follow the method of the proof of Lemma 2.

Neil Tennant