Why should I switch to Python? - Infinity of Primes

[Dennis E. Hamilton]

The standard approach is a proof by contradiction starting from the
assumption that there is a largest prime.

It's usually one of the earliest proofs in books on Number Theory.  Euclid
provided a proof and a version is given in section 4.2 of "Concrete
Mathematics: A Foundation for Computer Science" by Ronald L. Graham, Donald
E. Knuth, and Oren Patashnik.  Addison-Wesley (Reading, MA: 1989).   ISBN
0-201-14236-8.

It goes something like this (matching the one that was already posted for
you):

1.	Assume P is the largest prime.

2.	Let Q be the product of all of the primes up to P: 2*3*5* ... *P

3.	The number Q+1 is not divisible by any of the primes that divide Q (they
each leave a remainder of 1).  Therefore Q+1 is a prime or there is some
other prime, larger than P (i.e., not among 2, 3, 5, ..., P), that divides
Q+1.  So P is not the largest prime.  QED.

This all stands on the fundamental theorem of arithmetic: that every integer
number is a product of primes in exactly one way.  That is, there is no
other factorization of Q into primes than the one shown in its definition,
and Q+1 must have a factorization into primes, even if only Q+1 itself and
1.  That is Exercise 1.2.4-21 in "The Art of Computer Programming, v.1:
Fundamental Algorithms," ed.3 by Donald E. Knuth.  Addison-Wesley (Reading,
MA: 1997).  ISBN 0-201-89683-4.

Perhaps an interesting, indirect quality of Python is that it is supported
in a community of interest where one can discuss topics like the one you
just raised.

-- Dennis


-----Original Message-----
From: python-list-admin at python.org
[mailto:python-list-admin at python.org]On Behalf Of Jim Richardson
Sent: Monday, April 03, 2000 23:15
To: python-list at python.org
Subject: Re: Why should I switch to Python?


On 02 Apr 2000 08:16:57 -0400,
 François Pinard, in the persona of <pinard at iro.umontreal.ca>,
 brought forth the following words...:

>"Tim Peters" <tim_one at email.msn.com> writes:
>
>> When in doubt, there's no substitute for exhaustive enumeration.
>
>Hmph!  Hope you do not doubt there is an infinite number of primes! :-)

Out of curiousity, how does one (mathematically) prove that?
(if this turns out to be one of those 12' blackboards full of greek
letters and funny squiggles, Ok, I cry uncle...)
--
Jim Richardson
	Anarchist, pagan and proud of it
WWW.eskimo.com/~warlock
	Linux, because life's too short for a buggy OS.

--
http://www.python.org/mailman/listinfo/python-list