Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is Prime Finite?

  1. Nov 17, 2004 #1

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    So is it?

    Something I have been thinking about lately.
     
  2. jcsd
  3. Nov 17, 2004 #2

    James R

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your question doesn't seem to make sense.

    Do you mean "Is there a finite number of prime numbers?"

    If so, the answer is no. It is easy to prove that there are infinitely many primes.
     
  4. Nov 17, 2004 #3

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    There is no formula for finding primes yet? Right?
     
  5. Nov 17, 2004 #4

    James R

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There are ways of checking if a given number is prime or not. There is no known formula which generates the nth prime from the number n, if that's what you mean.
     
  6. Nov 18, 2004 #5

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    Eratosthenes' Sieve is a process that will give you primes as large as you please. The only requirement is lots of time and patience! :-)
     
  7. Nov 18, 2004 #6
    What about factorisation? Does any formula exist which can factorise any numbers into primes, as large as we please? The last time I heard, the answer was no.
     
  8. Nov 18, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Yes there is a way of doing it, but it takes far too long to do.
     
  9. Nov 18, 2004 #8

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    There are formulas that explicitly give the nth prime, none of them are that useful though.
     
  10. Nov 18, 2004 #9

    James R

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Oops. My mistake, jcsd. I think you're right.
     
  11. Nov 18, 2004 #10
    It´s actually so simple that I can post it here:
    (1) Assume a nonempty finite set P of primes.
    (2) Let X be the product of all these primes.
    (3) X+1 does not divide by any element in P so P cannot be the set of all primes (as any number except One divides by at least one prime).
    As this is true for all nonempty finite sets P the number of primes must be infinite or zero (hint: It isn´t zero :tongue:)

    EDIT: Thank´s to Shmoe and StatusX for helping me out with my flawed and less elegant 1st approach.


    Formulas in the sense of "prime(n) = ... " or algorithms to determine it (the latter is trivial)? What do you mean by saying they are not usefull? Can you give links or names?
     
    Last edited: Nov 18, 2004
  12. Nov 18, 2004 #11

    StatusX

    User Avatar
    Homework Helper

    Technically, the third step should be "none of the primes in the list divide it, so your list could not have been complete." Your third step is not self-evident.
     
  13. Nov 18, 2004 #12

    jcsd

    User Avatar
    Science Advisor
    Gold Member


    Here's one:

    [tex]f(n) = \lfloor \theta^{3^n}\rfloor[/tex]

    where [itex]\theta[/itex] is Mill's constant.

    Infact Mathworld has an entry on such formulas:

    http://mathworld.wolfram.com/PrimeFormulas.html
     
  14. Nov 18, 2004 #13
    Bad example as it doesn´t give the n-th prime but the link is interesting, thanks.

    @StatusX: I don´t really see a problem with my post although I have to admit that I took that out of my head and didn´t bother to look up a more elegant proof somewhere. I will consider rephrasing what I wrote.
     
  15. Nov 18, 2004 #14

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Your conclusion in step 3 is false. For example if our list of primes is 2,3,5,7,11, 13, then X+1=3031=59*509, in other words it has divisors other than 1 and X+1. The consequence of how X is made from our list of primes is that X+1 has a prime divisor that is not on our list, and hence we get another prime.
     
  16. Nov 18, 2004 #15
    >> in other words it has divisors other than 1 and X+1

    Not if my list of primes I start with is complete which was the assumtpion I started from. However, I realize how and why my post was misleading and/or improperly written.

    Thanks for showing where the problem lied, I´ve edited the thing in a way StatusX proposed.
     
  17. Nov 18, 2004 #16

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    No, if you start with assuming a complete list of primes you still can't conclude that X+1 has no divisors other than 1 or itself, only that none of your primes divide it (there is a distinction here). Add this to an earlier result that every integer has a prime divisor and you have a contradiction (this prime divisor may or may not be X+1).
     
  18. Nov 18, 2004 #17

    kreil

    User Avatar
    Gold Member

    [tex]
    (K+2){1-[WZ+H+J-Q]^2-[(GK+2G+K+1)(H+J)+H-Z]^2-[2N+P+Q+Z-E]^2
    [/tex]
    [tex] -[16(K+1)^3(K+2)(N+1)^2+1-F^2]^2 [/tex]
    [tex] -[E^3(E+2)(A+1)^2+1-O^2]^2 [/tex]
    [tex] -[(A^2-1)Y^2+1-X^2]^2 [/tex]
    [tex] -[16R^2Y^4(A^2-1)+1-U^2]^2 [/tex]
    [tex] -[((A+U^2(U^2-A))^2-1) x (N+4DY)^2+1-(X+CU)^2]^2 [/tex]
    [tex] -[N+L+V-Y]^2 [/tex]
    [tex] -[(A^2-1)L^2+1-M^2]^2 [/tex]
    [tex] -[AI+K+1-L-I]^2 [/tex]
    [tex] -[P+L(A-N-1)+B(2AN+2A-N^2-2N-2)-M]^2 [/tex]
    [tex] -[Q+Y(A-P-1)+S(2AP+2A-P^2-2P-2)-X]^2 [/tex]
    [tex] -[Z+PL(A-P)+T(2AP-P^2-1)-PM]^2} [/tex]

    Those are all minus signs on the left.

    I guess the way it works is you plug 26 numbers in for each variable, A-Z, and after you plug in all the (infinitely many) combinations it spits out all of the primes. Some combinations don't work and produce negative numbers. Any positive number it produces will be a prime.
     
  19. Nov 19, 2004 #18

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    2*3*5*7*11*13 + 1 = 30 031

    Proof:
    All variables are whole numbers here
    x*y mod x = 0
    y*x mod x = 0
    y=z*t
    x*z*t mod x = 0
    X times any number mod x is 0 thus X times the product of any numbers mod X is 0 thus X times the product of any numbers plus 1 mod x = 1 if X is greater than 1
    x*z*t + 1 mod x = 1
    x*z*t + 1 mod z = 1
    x*z*t + 1 mod t = 1

    You can say x is 2, z is 3, and t is 5 if you like.
     
  20. Nov 19, 2004 #19

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Yes, I typo'd a zero into oblivion, thanks for the correction.


    I don't see how this shows you get 30031 though. It will only show 2*3*5*7*11*13+1 is congruent to 1 mod 2, 3, 5, 7, 11, and 13. There are infinitely many numbers that satisfy this. (even better-there are infinitely many primes which satisfy this)
     
  21. Nov 19, 2004 #20

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    The proof shows that
    (2*3*5*7*11*13 + 1) mod (2, 3, 5, 7, 11, or 13) = 1
    IE that it isn't divisible by any of them.

    I'll need to think of how to show it's not divisible by any others...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Is Prime Finite?
  1. Product of primes (Replies: 10)

  2. Germain primes (Replies: 1)

  3. Prime numbers (Replies: 8)

Loading...