
#1
May2909, 03:26 PM

P: 20

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
May2909, 03:28 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,886

Well, what, exactly, is "Euler's polynomial equation"? Don't you think that is important?




#3
May2909, 03:32 PM

P: 20

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?




#4
May2909, 04:09 PM

P: 891

euler's polynomial proof 



#5
May2909, 05:13 PM

P: 891

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]pP(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
May2909, 09:17 PM

P: 2,159

It is possible with polynomials in more variables, as the same wiki article points out:




#7
May3009, 02:50 AM

Sci Advisor
HW Helper
P: 9,398

That doesn't count  look at the restriction placed on both the input and output variables.




#8
May3009, 01:58 PM

P: 891





#9
May3009, 03:13 PM

P: 97

P(n) = n^2 + n + 41 =>
P(40) = 40^2 + 40 + 41 = 40 * 40 + 40 + 41 = 40 * 41 + 41 = 41 * 41 = composite. 



#10
May3009, 06:01 PM

Sci Advisor
HW Helper
P: 3,680





#11
May3109, 03:28 AM

PF Gold
P: 1,059

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] 



#12
May3109, 07:26 AM

P: 2,159





#13
May3109, 10:33 AM

Sci Advisor
HW Helper
P: 3,680





#14
May3109, 03:09 PM

P: 891





#15
May3109, 06:34 PM

Sci Advisor
HW Helper
P: 3,680

If you do, I'd appreciate the effort if you post it.



Register to reply 
Related Discussions  
Proof of orthogonality of associated Legendre polynomial  Calculus  10  
Proof about an odd degree polynomial  Linear & Abstract Algebra  2  
Complex Analysis Proof showing that a Polynomial is linear  Calculus & Beyond Homework  4  
Irreducible polynomial on polynomial ring  Calculus & Beyond Homework  1  
Polynomial Proof  Linear & Abstract Algebra  3 