Why should I switch to Python? - Infinity of Primes
Charles G. Waldman
cgw at alum.mit.edu
Wed Apr 5 01:56:09 CEST 2000
In article <NDBBKEGCNONMNKGDINPFGEJDDFAA.infonuovo at email.com>, "Dennis E.
Hamilton" <infonuovo at email.com> wrote:
> 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
> 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 Exercise 1.2.4-21 in "The Art of Computer Programming, v.1
I'm pretty sure that this last statement is not correct.
You don't need unique factorization here. Euclid's proof does not require
a hypothesis of unique factorization into primes, just a well-ordering of
primes, and existence of division-with-remainder.
You just need the fact that when you divide A into (A*B)+1, you get a
remainder of 1. That's enough to show that none of the primes
2..P divide Q=1+(2*3*5*7..*P).
Since none of these primes divide Q, either Q is prime, or some other prime not
in the list 2..P divides Q, either of which options contradicts the hypothesis that
Q is the largest prime. Where do you need to make use of the fact that prime
factorizations are unique? Euclid's proof is self-contained and referencing
Knuth for a proof of unique factorization just muddies the waters.
Interestingly, there are some quadratic number fields (discrete subsets of the
complex numbers) which don't have unique factorization, but still have infinitely
many prime elements.
More information about the Python-list