Loading ...
Sorry, an error occurred while loading the content.

13947RE: [PrimeNumbers] Infinite primes-> a Turing Machine prime sieve that never stops?

Expand Messages
  • Paul Leyland
    Nov 4, 2003
      > From: Roger Bagula [mailto:tftn@...]

      > 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.

      Very well, time for another argument. It would be helpful if
      you respond (concisely and politely please) to each of the
      questions below.

      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
      we wish?

      If not, why not? I can try to make it clearer. If you do agree,
      let's proceed.

      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.

    • Show all 21 messages in this topic