Why should I switch to Python? - Infinity of Primes
Dennis E. Hamilton
infonuovo at email.com
Tue Apr 4 08:49:32 EDT 2000
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
It goes something like this (matching the one that was already posted for
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
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...)
Anarchist, pagan and proud of it
Linux, because life's too short for a buggy OS.
More information about the Python-list