Newsgroups: sci.math
From: hoey@ai.etl.army.mil (Dan Hoey)
Date: 14 Aug 90 22:06:23 GMT
Subject: Re: Euclid's proof

tor...@sics.se (Torkel Franzen) quotes from Euclid:

> Let A, B, C be the assigned prime numbers; I say that there are more
> prime numbers than A, B, C.
> For let the least numbered measured by A, B, C be taken, and let it be
> DE; let the unit DF be added to DE.
> Then EF is either prime or not.
> First, let it be prime; then the prime numbers A,B,C,EF have been found
> which are more than A,B,C.
> Next, let EF not be prime; therefore it ... [has a prime factor] G.
> I say that G is not the same with any of the numbers A,B,C....

Torkel continues:

>The formulation seems to be nearer the constructive one, i.e. for any
>finite set of primes a larger one can be found....

which misstates the result.  Euclid has shown for any finite set of
primes a *different* one can be found.  He does not (erroneously)
prove that ABC+1 is prime.  But when ABC+1 is composite, he shows
that any prime factor of ABC+1 must be different from A, B, and C.

cos...@bbn.com (Bernie Cosell) writes:

>you can *not* use the same logic to say anything about
>the subsequent product A*B*C*(ABC + 1)  +  1.

Wrong.  If ABC+1 is prime, then A*B*C*(ABC + 1) + 1 is either prime or
has a prime factor different from A,B,C,(ABC+1).  If not, then ABC+1
has a prime factor G, and ABCG+1 is either prime or has a prime factor
different from A,B,C,G.

But, originally, i...@Gang-of-Four.Stanford.EDU (Ilan Vardi) asked:

>It seems interesting whether Euclid considered his proof of an
>infinite number of primes as a proof by contradiction only, or
>whether he actually thought about it as a constructive proof.

Lest you infer that the proof is constructive, it should be noted that
the rest of Euclid's proof--that G (the prime factor of ABC+1) is
not among the previously found primes A,B,C--is in fact a proof by
contradiction.  I don't know if that proof could be turned into a
constructive one.

Dan