Guest Posted August 20, 2009 Report Share Posted August 20, 2009 Given a polynomial of the form, F(x) = c0 + c1x1 + c2x2 + .. + cnxn such that F(N) is a positive integer for any positive integer N, Then, F(x) can not generate only primes for x = 1, 2, 3.. This is a reasonably well known result. Can you prove it? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 20, 2009 Report Share Posted August 20, 2009 Then, F(x) can not generate only primes for x = 1, 2, 3.. what? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 20, 2009 Report Share Posted August 20, 2009 what? Then, F(x) can not generate only primes for x = 1, 2, 3.... Hope it is clear --------------- "..Which part of this don't you understand?.." - Death Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 20, 2009 Report Share Posted August 20, 2009 When x = yc0 (c0 times any y) then the polynomial will have c0 and 1 + c1y + c2c01y2 + .. + cnc0n-1yn as factors. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 20, 2009 Report Share Posted August 20, 2009 When x = yc0 (c0 times any y) then the polynomial will have c0 and 1 + c1y + c2c01y2 + .. + cnc0n-1yn as factors. Suppose c0 = 1. Then what? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 20, 2009 Report Share Posted August 20, 2009 (edited) Is this right? If such a polynomial existed, then F(1) would evaluate to some prime p. Consider F(1 + kp) where k is a positive integer. By the Fundamental Theorem of Algebra we can write F(x) as the product of linear terms ( I neglect quadratic terms because I'm confident that we are dealing with only real numbers). F(x) = b0(x-b1)(x-b2)... F(1) = b0(1-b1)(1-b2)... F(1+kp) = b0(1-b1+kp)(1-b2+kp)... Distributing the kp's out: One step: b0[ (1-b1)(1-b2+kp)(1-b3+kp)... + kp(1-b2+kp)(1-b3+kp)...] Working on the left term once again: b0[ (1-b1){ (1-b2)(1-b3+kp)(1-b4+kp)... + kp(1-b3+kp)(1-b4+kp)...} + kp(1-b2+kp)(1-b3+kp)...] By examining this pattern, we can see that we can remove the kp's from the original product term with the consequence of adding an additional term that is a multiple of kp. Assuming that the polynomial is of finite degree, we can continue to perform this algorithm on the expression and end up with b0(1-b1)(1-b2)(1-b3)... + b0*kp*(...Some big expression...) The left term here is simple F(1) which is also equal to p. F(1+kp) therefore equals p + b0*kp*(...) = p*(1 +k*b0*(...)) which is divisible by p. These F(1+kp) will be composite numbers with p as a factor unless they are all equal to p, in which case you have simply a constant function F(x) = p; This trivial case does not seem like a fair answer to the question. Edited August 20, 2009 by mmiguel1 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 Is this right? If such a polynomial existed, then F(1) would evaluate to some prime p. Consider F(1 + kp) where k is a positive integer. By the Fundamental Theorem of Algebra we can write F(x) as the product of linear terms ( I neglect quadratic terms because I'm confident that we are dealing with only real numbers). F(x) = b0(x-b1)(x-b2)... F(1) = b0(1-b1)(1-b2)... F(1+kp) = b0(1-b1+kp)(1-b2+kp)... Distributing the kp's out: One step: b0[ (1-b1)(1-b2+kp)(1-b3+kp)... + kp(1-b2+kp)(1-b3+kp)...] Working on the left term once again: b0[ (1-b1){ (1-b2)(1-b3+kp)(1-b4+kp)... + kp(1-b3+kp)(1-b4+kp)...} + kp(1-b2+kp)(1-b3+kp)...] By examining this pattern, we can see that we can remove the kp's from the original product term with the consequence of adding an additional term that is a multiple of kp. Assuming that the polynomial is of finite degree, we can continue to perform this algorithm on the expression and end up with b0(1-b1)(1-b2)(1-b3)... + b0*kp*(...Some big expression...) The left term here is simple F(1) which is also equal to p. F(1+kp) therefore equals p + b0*kp*(...) = p*(1 +k*b0*(...)) which is divisible by p. These F(1+kp) will be composite numbers with p as a factor unless they are all equal to p, in which case you have simply a constant function F(x) = p; This trivial case does not seem like a fair answer to the question. Brilliant! I should have clarified that F(x) is not a constant function. The solution that I know is similar in spirit, but a little simpler on analysis. Use reminder theorem. ..is, F(x + q.F(x)) is divisible by F(x) for any q, by reminder theorem. i.e, if F(x) = 0, F(x+q.F(x)) = F(x) = 0. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 My comments do not need a spoiler. 1. I loved that accidental typo about the "Reminder" theorem, methinks. Unintentionaly brilliant that !!! 2. I remember that some medi-aeval monk thought that the quadratic n*n + n + 41 was prime for all positive integers. It actually seems to work for the first few integers, but not when n reaches 40. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 My comments do not need a spoiler. 1. I loved that accidental typo about the "Reminder" theorem, methinks. Unintentionaly brilliant that !!! Oops! Sorry, I stand corrected Quote Link to comment Share on other sites More sharing options...
Question
Guest
Given a polynomial of the form,
F(x) = c0 + c1x1 + c2x2 + .. + cnxn
such that F(N) is a positive integer for any positive integer N,
Then, F(x) can not generate only primes for x = 1, 2, 3..
This is a reasonably well known result.
Can you prove it?
Link to comment
Share on other sites
8 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.