Re: Is there a largest prime number?
N. Silver
> Now, while I realize that I haven't disproved the hypothesis that there
> are infinitely many prime numbers, Euclid's 'proof' no longer satisfies
> me.
Given three primes, Euclid constructs
another number that is not divisible by
any of the three primes.
http://aleph0.clarku.edu/%7Edjoyce/java/elements/bookIX/propIX20.html
N. Silver
> This is Euclid's analysis:
> Every prime number, when divided into this number, leaves a remainder of
> one. So this number has no prime factors (remember, by assumption, it's
> not prime itself). This is a contradiction. Thus there must, in fact, be
> infinitely many primes.
Euclid breaks his proof into two cases.
Your analysis is not Euclid's.
http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
Richard Henry
"Richard Cavell" <richar...@mail.com> wrote in message
news:cva6kv$nkj$1...@nnrp.waia.asn.au...
> Hi,
>
> It is said that there is no largest prime number. Imagine you had a
> list of all the prime numbers (2,3,5,7,11... P), where P were what
> you're calling the largest prime number.
>
> x = (2*3*5*7*11*...*P)+1
>
> This is Euclid's analysis:
> Every prime number, when divided into this number, leaves a remainder of
> one. So this number has no prime factors (remember, by assumption, it's
> not prime itself). This is a contradiction. Thus there must, in fact, be
> infinitely many primes.
>
>
> 2*3*5*7*11*13+1 = 30031 = 59 x 509
> 2*3*5*7*11*13*17+1 = 510511 = 19 x 97 x 277
> etc.
>
> So if I were to take 13 or 17 as the 'largest prime number', it turns
> out that x DOES have prime factors, which are in fact larger than what I
> thought was the 'largest prime number'.
>
> Now, while I realize that I haven't disproved the hypothesis that there
> are infinitely many prime numbers, Euclid's 'proof' no longer satisfies
me.
Why are you not satisifed? Your statement "x DOES have prime factors, which
are in fact larger than what I thought was the 'largest prime number'"
confirms Euclid's analysis.
robert j. kolker
Richard Cavell wrote:
>
> Now, while I realize that I haven't disproved the hypothesis that there
> are infinitely many prime numbers, Euclid's 'proof' no longer satisfies me.
Why? It is a correct proof by contradiction. The assumption of a largest
prime leads directly to a contradiction. There are other proofs. There
is one using the Riemann Zeta Function.
Bob Kolker
Anthony Buckland
> Hi,
>
> It is said that there is no largest prime number. Imagine you had a
> list of all the prime numbers (2,3,5,7,11... P), where P were what
> you're calling the largest prime number.
>
> x = (2*3*5*7*11*...*P)+1
>
> This is Euclid's analysis:
> Every prime number, when divided into this number, leaves a remainder
> of one. So this number has no prime factors (remember, by assumption,
> it's not prime itself). This is a contradiction. Thus there must, in
> fact, be infinitely many primes.
>
> Now, I'd like to point out that
>
> 2*3*5*7*11*13+1 = 30031 = 59 x 509
> 2*3*5*7*11*13*17+1 = 510511 = 19 x 97 x 277
> etc.
>
> So if I were to take 13 or 17 as the 'largest prime number', it turns
> out that x DOES have prime factors, which are in fact larger than what
> I thought was the 'largest prime number'.
>
> Now, while I realize that I haven't disproved the hypothesis that
> there are infinitely many prime numbers, Euclid's 'proof' no longer
> satisfies me.
You've found contradictions to the hypotheses that two specific numbers
might be
the largest prime number. Euclid proved the general case, which is much
better.
Richard Cavell
Alec McKenzie
> It is said that there is no largest prime number. Imagine you had a
> list of all the prime numbers (2,3,5,7,11... P), where P were what
> you're calling the largest prime number.
>
> x = (2*3*5*7*11*...*P)+1
>
> This is Euclid's analysis:
> Every prime number, when divided into this number, leaves a remainder of
> one. So this number has no prime factors (remember, by assumption, it's
> not prime itself). This is a contradiction. Thus there must, in fact, be
> infinitely many primes.
That is not Euclid's analysis.
In the first place there was no concept of 'infinitely many' in
his day, and what he proved was that for every prime there
exists a larger prime.
Secondly, he does not say "this number has no prime factors",
which as you point out need not be true. What he says is that if
there are prime factors of P, the smallest of them must be
larger than P. This *is* true, and proves the existence of a
prime larger than P.
--
Alec McKenzie
mcke...@despammed.com
Bill Dubuque
Keep in mind that proofs by contradiction can yield all sorts
of false results. For example, we can convert the above proof
to show that if there are a finite number of primes then their
product is zero. Namely, recall one easily proves by induction
that every positive integer > 1 has a prime factor. Now x above
is clearly positive, but has no prime factors, so x = 1. Hence
2*3*5*...*P = 0. Similarly, we may continue, deducing any false
statement we desire. E.g. canceling shows every prime equals 0,
hence from 2 = 0, 3 = 0 we derive 1 = 0 by subtraction; etc.
Such absurdity is standard fare for proofs by contradiction.
If you find this a bit too confusing you may prefer to recast
the proof into non-contradictory form. In this interpretation
the proof shows that given any finite set S of primes there
exists another prime not in S, so the set of primes does not
have finite cardinality. This is the form that Euclid proved:
http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
--Bill Dubuque
N. Silver
> This is the form that Euclid proved:
> http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
Thanks for finding that, Bill.
Arturo Magidin
Richard Cavell <richar...@mail.com> wrote:
>Hi,
>
>It is said that there is no largest prime number. Imagine you had a
>list of all the prime numbers (2,3,5,7,11... P), where P were what
>you're calling the largest prime number.
>
>x = (2*3*5*7*11*...*P)+1
>
>This is Euclid's analysis:
>Every prime number, when divided into this number, leaves a remainder of
>one. So this number has no prime factors (remember, by assumption, it's
>not prime itself). This is a contradiction. Thus there must, in fact, be
>infinitely many primes.
I disagree that this is Euclid's analysis. It is a reasonable enough
way to prove it by contradiction, though.
>Now, I'd like to point out that
>
>2*3*5*7*11*13+1 = 30031 = 59 x 509
>2*3*5*7*11*13*17+1 = 510511 = 19 x 97 x 277
>etc.
>
>So if I were to take 13 or 17 as the 'largest prime number', it turns
>out that x DOES have prime factors, which are in fact larger than what I
>thought was the 'largest prime number'.
I don't see what the problem is. Are you under the impression that
Euclid argued that 2*3*...*P + 1 was itself a prime? No.
His precise argument is in Proposition 20 of Book IX, e.g.
http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
His argument is: say you are given three prime numbers A, B, and
C. Let D be the least common multiple of A, B, and C (which, of
course, is their product ABC), and let E = D+1.
Then either E is prime or not.
If E is prime, then E is not any of the numbers A, B, or C, so we have
found one more prime than A, B, and C.
If E is not prime, then it must be divisible by some prime G (this is
Proposition 32 in Book VII,
http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html
)
Then he claims that G is none of A, B, or C. For assume that G were
equal to some of A, B, or C. Then since A, B, and C all divide D, and
G is one of them, then G would divide D. But since G also divides E,
then it would divide the difference of E and D, E-D. Since E= D+1,
then G would divide 1, which is absurd.
Therefore, G is none of A, B, nor C, and by hypothesis is a prime. So
a prime number other than A, B, and C has been found.
Then he concludes (appealing implicitly to the obvious generalization
with more than 3 given primes) that "prime numbers are more than any
assigned multitude of prime numbers".
You'll note that he is not saying that the product plus 1 is prime,
nor is he assuming that the given primes are "all the primes". What he
is doing is showing that, given any finite list of primes, it is
always possible to implicitly exhibit a prime not on that list, namely
a prime divisor of (the product of all given primes) plus 1.
>
>Now, while I realize that I haven't disproved the hypothesis that there
>are infinitely many prime numbers, Euclid's 'proof' no longer satisfies me.
What exactly is it that does not satisfy you about the argument given
by Euclid (as opposed to the proof by contradiction you presented)?
And what exactly is it that does not satisfy you about the proof by
contradiction that you presented?
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Bill Dubuque
I mentioned that before [1] in a 2003/12/8 post on the same topic.
There I defended the correctness of the variant of Euler's proof
that reaches the contradiction that 1 + 2*3*5*...*P is prime.
This provides yet another illustration of the myriad possibilities
inherent in proofs by contradiction. As I said there: "Since we know
the integers so intimately, we've many well-known theorems as targets
for a contradiction. Such is the nature of proofs by contradiction."
I refer the o.p. to this long thread [1] (48 posts) for much further
discussion on this topic.
--Bill Dubuque
[1] http://google.com/groups?selm=y8zk756...@nestle.ai.mit.edu
http://groups-beta.google.com/group/sci.math/msg/b613e521425c702c