Can a Polynomial Equation Generate All Primes? A Proof for Euler's Polynomial

In summary: Euler's equation was going to generate all the primes. This was disproved in the 1800's using a counter example.
  • #1
khotsofalang
21
0
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?
 
Physics news on Phys.org
  • #2
Well, what, exactly, is "Euler's polynomial equation"? Don't you think that is important?
 
  • #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, isn't there any way he can be proven to be false?
 
  • #4
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?
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.
 
  • #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?
 
  • #6
It is possible with polynomials in more variables, as the same wiki article points out:

...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).
 
  • #7
That doesn't count - look at the restriction placed on both the input and output variables.
 
  • #8
Count Iblis said:
It is possible with polynomials in more variables, as the same wiki article points out:
but the same polynominal would generate composites also with large enough variables. Think how easy it would be to exceed the largest prime otherwise
 
  • #9
P(n) = n^2 + n + 41 =>
P(40) = 40^2 + 40 + 41
= 40 * 40 + 40 + 41
= 40 * 41 + 41 = 41 * 41 = composite.
 
  • #11
  • #12
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

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.
 
  • #13
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. [tex] Then P(1+kS) \equiv P(1) \equiv 0 Mod S.[/tex]

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.
 
  • #14
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.
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.
 
  • #15
If you do, I'd appreciate the effort if you post it.
 

1. What is Euler's polynomial proof?

Euler's polynomial proof is a mathematical proof developed by Swiss mathematician Leonhard Euler in the 18th century. It is a method for solving polynomial equations and finding the roots of the equation.

2. How does Euler's polynomial proof work?

Euler's polynomial proof involves re-writing the polynomial equation in a specific form, known as the Euler form. This form allows for the roots of the equation to be easily identified and solved.

3. What are the benefits of using Euler's polynomial proof?

Euler's polynomial proof is a systematic and efficient method for solving polynomial equations. It can also be used to find multiple roots of an equation at once, making it a useful tool for mathematicians and scientists.

4. Are there any limitations to Euler's polynomial proof?

While Euler's polynomial proof is a powerful tool for solving polynomial equations, it is limited to only working for equations with real coefficients. It also does not work for polynomials of degree higher than 4.

5. How is Euler's polynomial proof relevant in modern mathematics?

Euler's polynomial proof is still used today in various fields of mathematics, such as algebra, number theory, and calculus. It serves as a foundational method for solving polynomial equations and has paved the way for further developments in the field of mathematics.

Similar threads

  • Linear and Abstract Algebra
Replies
5
Views
877
Replies
4
Views
875
  • Linear and Abstract Algebra
Replies
2
Views
913
  • Linear and Abstract Algebra
Replies
2
Views
918
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
1K
  • Differential Equations
Replies
1
Views
1K
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
3K
Back
Top