Euler's polynomial equation P(n) = n² + n + 41 does not generate all prime numbers, as proven by counterexamples. A general theorem states that no polynomial can produce only prime numbers for all positive integers. The discussion references a proof that shows if P(x) yields a prime p for n, then P(n + kp) is composite for all integers k, indicating that the polynomial is constant rather than a true polynomial. Additionally, while polynomials in multiple variables can generate primes, they also produce composite numbers, especially as variable sizes increase.
PREREQUISITESMathematicians, number theorists, and anyone interested in the relationship between polynomials and prime number generation.
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.khotsofalang said: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, isn't there any way he can be proven to be false?
...is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by this polynomial inequality as the variables a, b, …, z range over the nonnegative integers.
A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables. Hence, there is a prime-generating polynomial as above with only 10 variables. However, its degree is large (in the order of 10^45). On the other hand, there also exists such a set of equations of degree only 4, but in 58 variables (Jones 1982).
but the same polynominal would generate composites also with large enough variables. Think how easy it would be to exceed the largest prime otherwiseCount Iblis said:It is possible with polynomials in more variables, as the same wiki article points out:
ramsey2879 said: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
ramsey2879 said:but the same polynominal would generate composites also with large enough variables. Think how easy it would be to exceed the largest prime otherwise
robert Ihnot said:That no polynominal can generate all primes is easily shown using the reference given already http://en.wikipedia.org/wiki/Formula_for_primes
Let P(1) = a prime S. Then P(1+kS) \equiv P(1) \equiv 0 Mod S.
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.CRGreathouse said: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.