13947RE: [PrimeNumbers] Infinite primes-> a Turing Machine prime sieve that never stops?
- Nov 4, 2003
> From: Roger Bagula [mailto:tftn@...]Very well, time for another argument. It would be helpful if
> The sequences related to Euclid's proof are:
> A000945 A000946 A002585 A005265 A005266 A051342
> ( there are several new ones as well)
> A00945 is just the first "related" sequence.
> But there have to be two schools of thought
> since "proof" isn't working.
> 1) Euclid's school infinite primes exist
> 2) modern school of thought : infinite primes don't exist
> Unless you can "conclusively" prove no infinite prime exists...
> I've seen nothing like that in the posts.
> It can be "argued" both ways. Paul Leyland
> is good at arguing, but lacks conclusive proofs to go
> with it.
you respond (concisely and politely please) to each of the
First my thesis: infinite primes do not exist. The set of
primes is infinite (because it has cardinality aleph_0).
Consider carefully the difference between these two statements.
The first says that, because infinity is not an integer and primes
are integers, the concept "infinite prime" is meaningless. The
second says that the set of primes can be put in one-to-one
correspondence with the set of integers >0.
Yuo do not seem to like the classical proof, so let's prove the
number of primes (i.e the cardinality of the set of primes) is
infinite by another approach.
Do you agree that the set of natural numbers is infinite?
That is, do you believe that given a particular integer N, we can
always find a larger integer M, no matter how large N may be?
Do you agree that, given N, the value M=N+1 is larger than N?
Again, if not the game is over because we are not talking about
mathematics as understood by almost all the world's mathematicians.
Do you agree that each and every integer N > 1 has a unique
factorization into primes?
I'm concerned only with which primes appear in the factorization,
not with the order in which they are given. Numerical order is
conventional but it really doesn't matter which order they are in
for the arguments below.
Next, I am going to define F_N, where N is an integer > 0, to be
the value 2^(2^N)+1, so F_1 has the value 5, F_2 has the value 17,
F_3 has the value 257, F_4 has the value 65537, and so on.
Do you agree that the set of all values F_N is infinite?
I claim it is because the N can take any integer value and each
value of N yields a value for F_N.
Do you agree that all the values for F_N are distinct?
I claim they are because 2^N is larger than N, and 2^(2^N) is
larger than 2^N. I therefore claim that each F_i is greater
than F_j whenever i>j.
Do you agree that (x+y)*(x-y) = x^2 - y^2?
Now, let's take a look at F_N - 2. By definition of F_N, this
quantity is equal to 2^(2^N) - 1. Note that 1 is a square (it is
1 squared and that 2^(2^N) is a square (it is 2^(2^(N-1)) squared.)
So, do you agree that the following equation is correct?
F_N - 2 = (2^(2^(N-1)) + 1) * ( 2^(2^(N-1)) - 1)
If so, you will readily conclude that the first term is just the
definition of F_(N-1), and the second is just F_(N-1) - 2).
Now what does this tell us? (A rhetorical question, no need to
answer). It says that F_N - 2 is a multiple of F_(N-1). Of course,
we have to be careful. F_i is not defined if i is less than 1, so
we have to insist that N >= 2 in the above equation. So lets start
with N=2 and work our way up.
When N=2, F_2 - 2 = F_1 * (F_1 - 2).
This is easy to check:
F_2 is 17, F_1 is 5 and, indeed F_2-2 = 15 = 5*3 = F_1 * (F_1 -2).
When N=3, F_3 - 2 = 255
= F_2 * (F_2 - 2)
= 17 * F_1 * (F_1 - 2)
= 17 * 5 * 3.
When N = 4, F_4 - 2 = 65535
= F_3 * (F_3 - 2)
= 257 * F_2 * (F_2 - 2)
= 257 * 17 * F_1 * (F_1 - 2)
= 257 * 17 * 5 * 3.
With me so far? Do you agree that we can continue this process
as far as we wish, because we can increase the value of N as far as
If not, why not? I can try to make it clearer. If you do agree,
I now claim that F_M has no prime factors in common with *any* F_N
for which N < M. The reasoning is that F_M - 2 is a multiple of
all F_N for which N < M. Thus, any prime factor of F_N yields a
remainder of 2 when divided into F_M. All the F_N numbers are odd,
so we can discount the prime number 2 as being a factor of any of them.
Do you agree with this claim? If not, please explain what you think
is wrong with it.
Assuming you do agree, you will also agree that I have produced an
infinite set of numbers, none of which share a common prime factor.
The set of all F_N consists only of integers, so each and every one
has at least one prime factor, agreed?
But as the set of all F_N has cardinality aleph_0, the same as the
cardinality of the set of all integers >=1, AND every member of the
set of all F_N is an integer, AND every member of the set of all F_N
has at least one prime factor, AND no two members share any prime
factors, THEN the cardinality of the set of all prime factors of all
the members of the set of all F_N is itself aleph_0.
What does the above lengthy and pedantically stated sentence say
(another rhetorical question)? It says that we have constructed
a set of prime numbers which has cardinality aleph_0. That is,
we've found an infinite set of prime numbers. This, I claim, proves
my thesis given at the start of this article. Note I do *not* claim
that the set of primes I constructed contains all the primes. In fact,
we know for certain that it does not, and you should be able to prove
that, for instance, neither 2 nor 13 are members of the set.
Nonetheless, it is an infinite set.
Conclusion: the set of all primes is infinite (has cardinality
aleph_0) because at least one set which contains only primes itself
has cardinality aleph_0.
- << Previous post in topic Next post in topic >>