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

Euler's polynomial proof

  1. May 29, 2009 #1
    without using a counter example, show a proof that Euler's polynomial equation P(n)=n^2+n+41 can not be used to generate all the primes.can a general proof be made to show that all primes cannot be generated by a specific polynomial?
     
  2. jcsd
  3. May 29, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, what, exactly, is "Euler's polynomial equation"? Don't you think that is important?
     
  4. May 29, 2009 #3
    thats the proposition made by Euler that P(n)=n^2+n+41 can generate all primes and it was suddenly proven false by using a counter example, isnt there any way he can be proven to be false?
     
  5. May 29, 2009 #4
    I believe you mean that P(n) would be prime for positive integers n, but there is now a general proof out there that no polynominal equation can generate only primes for all positive integers. I am sure that someone can cive you a link to a proof.
     
  6. May 29, 2009 #5
    See also http://en.wikipedia.org/wiki/Formula_for_primes Euler's formula for primes as posted in this thread was once widely thought to generate primes for any integer n, but as shown by this link that was false. The proof is simple an noted in the link. Assume that P(x) is a polynominal in x that gives a prime [tex]p[/tex] for the value [tex]n[/tex].
    But then [tex]p|P(n+kp)[/tex] for all integer [tex]k[/tex] so these numbers must be composite for every k so the polynominal is a constant, p, rather than a polynominal.

    P.S. Euler never said that the polynominal generated "all primes", but then that is obviously not what you meant is it?
     
  7. May 29, 2009 #6
    It is possible with polynomials in more variables, as the same wiki article points out:

     
  8. May 30, 2009 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    That doesn't count - look at the restriction placed on both the input and output variables.
     
  9. May 30, 2009 #8
    but the same polynominal would generate composites also with large enough variables. Think how easy it would be to exceed the largest prime otherwise
     
  10. May 30, 2009 #9
    P(n) = n^2 + n + 41 =>
    P(40) = 40^2 + 40 + 41
    = 40 * 40 + 40 + 41
    = 40 * 41 + 41 = 41 * 41 = composite.
     
  11. May 30, 2009 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

  12. May 31, 2009 #11
  13. May 31, 2009 #12
    The positive values of the Jones polynomial for positive values of the variables are always primes and all primes can be obtained this way. The problem is just that the probability that a random choice of the input vaiables will yield a positive value is astronomically small. If finally, after billions of years of trying, some positive value is obtained, it will likely be a prime number like 23.
     
  14. May 31, 2009 #13

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Was that in response to my post? I was incredulous about the claim that "once widely thought to generate primes for any integer n". It's obvious that no nonconstant polynomial can produce primes for all n, so it's hard for me to believe that this was ever believed. But it could be true, so I was looking for ramsey2879 or someone else to comment on that.
     
  15. May 31, 2009 #14
    I am 60 and some years old so I some times don't remember exactly what I read too well. The book is up in the attic. Some time I will look again at what was said about the polynominal. But that the polynominal does give composite values is of course easily shown.
     
  16. May 31, 2009 #15

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    If you do, I'd appreciate the effort if you post it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Euler's polynomial proof
  1. Polynomial Proof (Replies: 3)

Loading...