1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...
     
  22. Nov 19, 2004 #21
    Good luck, because as shmoe said, it's divisible by 59 and 509.
     
  23. Nov 19, 2004 #22

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I see. From the format of your post it looked like you were trying to prove that 2*3*5*7*11*13+1=30,031. I wasn't disagreeing that X+1 wouldn't have any prime factors from the original list (I said as much) so it didn't cross my mind that you were trying to prove this.

    That was the point of my example, you can't show X+1 has only the trivial divisors since it's not in general true. The X+1 that you get is not necessarily prime. Though I botched a zero, the 59*509 factorization is still correct for that list of primes.
     
  24. Nov 19, 2004 #23

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    Well then think of it this way:

    Since the number does not have any factors in the primes we counted (up to 13), we know that it has no factors which have factors in the known primes.

    MEANING if it has a factor, that factor which is prime which is above our known primes! (if that factor is not prime, it means it has a factor which is prime or that factor has a fac..)

    x*y*z + 1 mod (x,y or z) = 1 so x,y and z are not factors
    thus if x*y*z + 1 has any factors, this factor will not have factors x,y or z
    thus we must reach some factor which has no factors, or a prime
     
    Last edited: Nov 19, 2004
  25. Nov 20, 2004 #24
    Think of a prime number as being a gap between the product of a number of primes (composite numbers). Because there is an infinitie number of composites, there will be an infinite number of gaps and thus an infinite number of primes.
     
  26. Nov 21, 2004 #25

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You're not a mathematician, right? Presuming there to be an infinite number of "gaps" since there are an infinite number of composites? Short of proving that there are an infinite number of gaps (ie primes) I don't see why anyone should accept that hypothesis.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook